codeforces-scrape

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

378B.md (2738B)


      1 Source: https://codeforces.com/problemset/problem/378/B
      2 
      3 B. Semifinals
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Two semifinals have just been in the running tournament. Each semifinal had *n* participants. There are *n* participants advancing to the finals, they are chosen as follows: from each semifinal, we choose *k* people (0 ≤ 2*k* ≤ *n*) who showed the best result in their semifinals and all other places in the finals go to the people who haven't ranked in the top *k* in their semifinal but got to the *n* - 2*k* of the best among the others.
     22 
     23 The tournament organizers hasn't yet determined the *k* value, so the participants want to know who else has any chance to get to the finals and who can go home.
     24 
     25 Input
     26 
     27 The first line contains a single integer *n* (1 ≤ *n* ≤ 105) — the number of participants in each semifinal.
     28 
     29 Each of the next *n* lines contains two integers *a**i* and *b**i* (1 ≤ *a**i*, *b**i* ≤ 109) — the results of the *i*-th participant (the number of milliseconds he needs to cover the semifinals distance) of the first and second semifinals, correspondingly. All results are distinct. Sequences *a*1, *a*2, ..., *a**n* and *b*1, *b*2, ..., *b**n* are sorted in ascending order, i.e. in the order the participants finished in the corresponding semifinal.
     30 
     31 Output
     32 
     33 Print two strings consisting of *n* characters, each equals either "0" or "1". The first line should correspond to the participants of the first semifinal, the second line should correspond to the participants of the second semifinal. The *i*-th character in the *j*-th line should equal "1" if the *i*-th participant of the *j*-th semifinal has any chances to advance to the finals, otherwise it should equal a "0".
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4  
     41 9840 9920  
     42 9860 9980  
     43 9930 10020  
     44 10040 10090
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 1110  
     51 1100
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4  
     58 9900 9850  
     59 9940 9930  
     60 10000 10020  
     61 10060 10110
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 1100  
     68 1100
     69 ```
     70 
     71 Note
     72 
     73 Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090.
     74 
     75 * If *k* = 0, the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals.
     76 * If *k* = 1, the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds).
     77 * If *k* = 2, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.