codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2053B.md (2844B)


      1 Source: https://codeforces.com/problemset/problem/2053/B
      2 
      3 B. Outstanding Impressionist
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 If it was so, then let's make it a deal...
     22 
     23 — MayDay, [Gentleness](https://www.youtube.com/watch?v=mtAc_bMYBsM&list=PLj6NQzHFCvkHKIm0Vnk9LH3odqTIBRZ1Q&index=15)
     24 
     25 Even after copying the paintings from famous artists for ten years, unfortunately, Eric is still unable to become a skillful impressionist painter. He wants to forget something, but the white bear phenomenon just keeps hanging over him.
     26 
     27 Eric still remembers $n$ pieces of impressions in the form of an integer array. He records them as $w_1, w_2, \ldots, w_n$. However, he has a poor memory of the impressions. For each $1 \leq i \leq n$, he can only remember that $l_i \leq w_i \leq r_i$.
     28 
     29 Eric believes that impression $i$ is unique if and only if there exists a possible array $w_1, w_2, \ldots, w_n$ such that $w_i \neq w_j$ holds for all $1 \leq j \leq n$ with $j \neq i$.
     30 
     31 Please help Eric determine whether impression $i$ is unique for every $1 \leq i \leq n$, independently for each $i$. Perhaps your judgment can help rewrite the final story.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot 10^5$) — the number of impressions.
     38 
     39 Then $n$ lines follow, the $i$-th containing two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq 2\cdot n$) — the minimum possible value and the maximum possible value of $w_i$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output a binary string $s$ of length $n$: for each $1 \leq i \leq n$, if impression $i$ is unique, $s_i=\texttt{1}$; otherwise, $s_i=\texttt{0}$. Do not output spaces.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 2
     55 
     56 1 1
     57 
     58 1 1
     59 
     60 4
     61 
     62 1 3
     63 
     64 1 3
     65 
     66 1 3
     67 
     68 1 3
     69 
     70 6
     71 
     72 3 6
     73 
     74 2 2
     75 
     76 1 2
     77 
     78 1 1
     79 
     80 3 4
     81 
     82 2 2
     83 
     84 7
     85 
     86 3 4
     87 
     88 4 4
     89 
     90 4 4
     91 
     92 1 3
     93 
     94 2 5
     95 
     96 1 4
     97 
     98 2 2
     99 
    100 3
    101 
    102 4 5
    103 
    104 4 4
    105 
    106 5 5
    107 ```
    108 
    109 Output
    110 
    111 ```
    112 00
    113 1111
    114 100110
    115 1001111
    116 011
    117 ```
    118 
    119 Note
    120 
    121 In the first test case, the only possible array $w$ is $[1, 1]$, making neither impression $1$ nor $2$ unique (since $w_1 = w_2$).
    122 
    123 In the second test case, all impressions can be made unique:
    124 
    125 * For $i = 1$, we can set $w$ to $[1, 3, 2, 3]$, in which $w_1 \neq w_2$, $w_1 \neq w_3$, and $w_1 \neq w_4$;
    126 * For $i = 2$, we can set $w$ to $[2, 3, 1, 2]$, in which $w_2 \neq w_1$, $w_2 \neq w_3$, and $w_2 \neq w_4$;
    127 * For $i = 3$, we can set $w$ to $[1, 1, 3, 1]$;
    128 * For $i = 4$, we can set $w$ to $[2, 3, 3, 1]$.
    129 
    130 In the third test case, for $i = 4$, we can set $w$ to $[3, 2, 2, 1, 3, 2]$. Thus, impression $4$ is unique.