CCCHK '15 S5 - Can I pass the courses?

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.2s
Memory limit: 256M

Problem types

There are many students in the University of Hong Kong. Some of them are hardworking, some are clever and some are both hardworking and clever. We use two real numbers to describe a student. HWP (Hard Working Point) describes how hardworking she is, and CP (Clever Point) describes how clever she is.

There are many courses in the University of Hong Kong. For some of the courses, like physics, student must work very hard and do a lot of exercise to pass the course. So students with high HWP can pass it easily. Of course, if a student is clever, it also helps a little. For some other courses, like artificial intelligence, CP helps a lot and HWP helps a little. So we can also use two real numbers x and y to describe a course. A student can pass the course if and only if \displaystyle  \textbf{HWP}\times x + \textbf{CP}\times y > 1

There is a course management system, teachers can create new courses or cancel courses, and students can know if she can pass all the courses that exist right now.

Input specification:

The first line of the input contains one integer M, representing the number of operations.

Each of the following M lines contains some numbers describing an operation.

  • If the first number is 0, it means a teacher creates a new course. Then the following three numbers in this line are x,y,id of the course. (0.001 < x,y < 1000, 0 \leq id \leq 100000), and id is an integer)
  • If the first number is 1, it means a teacher cancels an old course. Then the following one number in this line represents the id of the course to cancel. It is guaranteed that this course exist before deleting.
  • If the first number is 2, it means a student wants to know if she can pass all the courses that exists right now, the following two number in this line are HWP and CP of the student. (0.001<\textbf{HWP},\textbf{CP}< 1000)

To avoid precision problems, for any student and any course, |\textbf{HWP}\times x + \textbf{CP}\times y - 1| > 10^{-8}.

  • For 20\% of the test cases, M \leq 1000.
  • For other 40\% of the test cases, there is no cancel operation.
  • For 100\% of the test cases, M \leq 100000.

Output specification:

For each student, if she can pass all the courses, print a line with single integer 1. Otherwise, print a line with single integer 0.

Sample Input 1

8
0 1 2 1
0 5 0.2 2
2 0.1 2
2 0.1 3
0 0.13 0.59 3
0 2.44 0.78 4
2 3 1
2 1 3

Sample Output 1

0
1
0
1

Sample Input 2

10
0 1 2 1
0 5 0.2 2
2 0.1 2
2 0.1 3
1 2
2 0.1 2
0 0.13 0.59 3
0 2.44 0.78 4
2 3 1
2 1 3

Sample Output 2

0
1
1
0
1

Comments

There are no comments at the moment.