codeforces-scrape

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

1100B.md (2019B)


      1 Source: https://codeforces.com/problemset/problem/1100/B
      2 
      3 B. Build a Contest
      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 Arkady coordinates rounds on some not really famous competitive programming platform. Each round features $n$ problems of distinct difficulty, the difficulties are numbered from $1$ to $n$.
     22 
     23 To hold a round Arkady needs $n$ new (not used previously) problems, one for each difficulty. As for now, Arkady creates all the problems himself, but unfortunately, he can't just create a problem of a desired difficulty. Instead, when he creates a problem, he evaluates its difficulty from $1$ to $n$ and puts it into the problems pool.
     24 
     25 At each moment when Arkady can choose a set of $n$ new problems of distinct difficulties from the pool, he holds a round with these problems and removes them from the pool. Arkady always creates one problem at a time, so if he can hold a round after creating a problem, he immediately does it.
     26 
     27 You are given a sequence of problems' difficulties in the order Arkady created them. For each problem, determine whether Arkady held the round right after creating this problem, or not. Initially the problems pool is empty.
     28 
     29 Input
     30 
     31 The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) — the number of difficulty levels and the number of problems Arkady created.
     32 
     33 The second line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$) — the problems' difficulties in the order Arkady created them.
     34 
     35 Output
     36 
     37 Print a line containing $m$ digits. The $i$-th digit should be $1$ if Arkady held the round after creation of the $i$-th problem, and $0$ otherwise.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 11
     45 2 3 1 2 2 2 3 2 2 3 1
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 00100000001
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4 8
     58 4 1 3 3 2 3 3 3
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 00001000
     65 ```
     66 
     67 Note
     68 
     69 In the first example Arkady held the round after the first three problems, because they are of distinct difficulties, and then only after the last problem.