| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 82 | 14 | 12 | 15.789% |
Benson the Rabbit likes towers. There are $N$ cities numbered 1ドル$ to $N,ドル and city $i$ is located at a point with integer coordinates $(X_i , Y_i)$. No two cities are located at the same point. Benson wants to build towers in some of these cities such that the following conditions are satisfied:
Benson knows that it is always possible to build towers satisfying these conditions, but does not know how he should do so. Help Benson determine where he should build the towers.
Your program must read from standard input.
The first line of the input contains one integer, $N,ドル the number of cities.
In the next $N$ lines, the $i$th line contains two integers $X_i,ドル $Y_i,ドル which means city $i$ is located at the point $(X_i , Y_i)$.
Your program must print to standard output.
Output one line containing a string of $N$ characters $A_1A_2 \cdots A_N$. $A_i$ should be 1ドル$ if Benson should build a tower in city $i,ドル and 0ドル$ otherwise. The towers built should satisfy all the conditions.
If there are several solutions your program can output any one of them.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $N ≤ 3$ |
| 2 | 11 | $N ≤ 16$ |
| 3 | 7 | $N = ab$ for some positive integers $a,ドル $b$ and $(X_{ai+j} , Y_{ai+j}) = (i + 1, j)$ for all integers $i,ドル $j$ with 0ドル ≤ i ≤ b - 1,ドル 1ドル ≤ j ≤ a$ |
| 4 | 6 | For every integer $a,ドル there are at most two cities whose $x$-coordinate is $a$. |
| 5 | 31 | $N ≤ 5000$ |
| 6 | 21 | $N ≤ 100000$ |
| 7 | 19 | - |
3 1 1 1 6 1 5
110
If we build towers in cities 1ドル$ and 2ドル$ which have the same $x$-coordinate, city 3ドル$ which also has the same $x$-coordinate lies on the line segment between them.
An example of an incorrect output would be 111ドル,ドル as there will be more than two towers having $x$-coordinate equal to 1ドル$ if towers are built in all 3ドル$ cities.
Another incorrect output is 101ドル,ドル as even though city 2ドル$ shares the same $y$-coordinate with cities 1ドル$ and 3ドル,ドル it does not lie on the line segment between them.
This testcase is valid for subtasks 1, 2, 5, 6, and 7.
6 1 1 1 2 2 1 2 2 3 1 3 2
110011
City 3ドル$ lies on the line segment between cities 1ドル$ and 5ドル$ which have the same $y$-coordinate, and city 4ドル$ lies on the line segment between cities 2ドル$ and 6ドル$ which have the same $y$-coordinate.
This testcase is valid for subtasks 2, 3, 4, 5, 6, and 7.
8 1 13 2 13 7 27 7 13 7 2 2 27 7 4 4 13
10101101
This testcase is valid for subtasks 2, 5, 6, and 7.