codeforces-scrape

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

2051C.md (2534B)


      1 Source: https://codeforces.com/problemset/problem/2051/C
      2 
      3 C. Preparing for the Exam
      4 
      5 time limit per test
      6 
      7 1.5 seconds
      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 Monocarp is preparing for his first exam at the university. There are $n$ different questions which can be asked during the exam, numbered from $1$ to $n$. There are $m$ different lists of questions; each list consists of exactly $n-1$ different questions. Each list $i$ is characterized by one integer $a_i$, which is the index of the only question which is not present in the $i$-th list. For example, if $n = 4$ and $a_i = 3$, the $i$-th list contains questions $[1, 2, 4]$.
     22 
     23 During the exam, Monocarp will receive one of these $m$ lists of questions. Then, the professor will make Monocarp answer all questions from the list. So, Monocarp will pass only if he knows all questions from the list.
     24 
     25 Monocarp knows the answers for $k$ questions $q_1, q_2, \dots, q_k$. For each list, determine if Monocarp will pass the exam if he receives that list.
     26 
     27 Input
     28 
     29 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 Each test case consists of three lines:
     32 
     33 * the first line contains three integers $n$, $m$ and $k$ ($2 \le n \le 3 \cdot 10^5$; $1 \le m, k \le n$);
     34 * the second line contains $m$ distinct integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$; $a_i \lt a_{i+1}$);
     35 * the third line contains $k$ distinct integers $q_1, q_2, \dots, q_k$ ($1 \le q_i \le n$; $q_i \lt q_{i+1}$).
     36 
     37 Additional constraints on the input:
     38 
     39 * the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print a string of $m$ characters. The $i$-th character should be 1 if Monocarp passes the exam if he receives the $i$-th question list, 0 if Monocarp won't pass.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 4 4 3
     53 
     54 1 2 3 4
     55 
     56 1 3 4
     57 
     58 5 4 3
     59 
     60 1 2 3 4
     61 
     62 1 3 4
     63 
     64 4 4 4
     65 
     66 1 2 3 4
     67 
     68 1 2 3 4
     69 
     70 2 2 1
     71 
     72 1 2
     73 
     74 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 0100
     81 0000
     82 1111
     83 10
     84 ```
     85 
     86 Note
     87 
     88 In the first test case, Monocarp knows the questions $[1, 3, 4]$. Let's consider all the question lists:
     89 
     90 * the first list consists of questions $[2, 3, 4]$. Monocarp doesn't know the $2$-nd question, so he won't pass;
     91 * the second list consists of questions $[1, 3, 4]$. Monocarp knows all these questions, so he will pass;
     92 * the third list consists of questions $[1, 2, 4]$. Monocarp doesn't know the $2$-nd question, so he won't pass;
     93 * the fourth list consists of questions $[1, 2, 3]$. Monocarp doesn't know the $2$-nd question, so he won't pass.