codeforces-scrape

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

500B.md (2852B)


      1 Source: https://codeforces.com/problemset/problem/500/B
      2 
      3 B. New Year Permutation
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 User ainta has a permutation *p*1, *p*2, ..., *p**n*. As the New Year is coming, he wants to make his permutation as pretty as possible.
     22 
     23 Permutation *a*1, *a*2, ..., *a**n* is prettier than permutation *b*1, *b*2, ..., *b**n*, if and only if there exists an integer *k* (1 ≤ *k* ≤ *n*) where *a*1 = *b*1, *a*2 = *b*2, ..., *a**k* - 1 = *b**k* - 1 and *a**k* < *b**k* all holds.
     24 
     25 As known, permutation *p* is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an *n* × *n* binary matrix *A*, user ainta can swap the values of *p**i* and *p**j* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*) if and only if *A**i*, *j* = 1.
     26 
     27 Given the permutation *p* and the matrix *A*, user ainta wants to know the prettiest permutation that he can obtain.
     28 
     29 Input
     30 
     31 The first line contains an integer *n* (1 ≤ *n* ≤ 300) — the size of the permutation *p*.
     32 
     33 The second line contains *n* space-separated integers *p*1, *p*2, ..., *p**n* — the permutation *p* that user ainta has. Each integer between 1 and *n* occurs exactly once in the given permutation.
     34 
     35 Next *n* lines describe the matrix *A*. The *i*-th line contains *n* characters '0' or '1' and describes the *i*-th row of *A*. The *j*-th character of the *i*-th line *A**i*, *j* is the element on the intersection of the *i*-th row and the *j*-th column of A. It is guaranteed that, for all integers *i*, *j* where 1 ≤ *i* < *j* ≤ *n*, *A**i*, *j* = *A**j*, *i* holds. Also, for all integers *i* where 1 ≤ *i* ≤ *n*, *A**i*, *i* = 0 holds.
     36 
     37 Output
     38 
     39 In the first and only line, print *n* space-separated integers, describing the prettiest permutation that can be obtained.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 7  
     47 5 2 4 3 6 7 1  
     48 0001001  
     49 0000000  
     50 0000010  
     51 1000001  
     52 0000000  
     53 0010000  
     54 1001000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1 2 4 3 6 7 5
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5  
     67 4 2 1 5 3  
     68 00100  
     69 00011  
     70 10010  
     71 01101  
     72 01010
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1 2 3 4 5
     79 ```
     80 
     81 Note
     82 
     83 In the first sample, the swap needed to obtain the prettiest permutation is: (*p*1, *p*7).
     84 
     85 In the second sample, the swaps needed to obtain the prettiest permutation is (*p*1, *p*3), (*p*4, *p*5), (*p*3, *p*4).
     86 
     87  ![](https://espresso.codeforces.com/ac59dc4637702db5659cc386bf71ba75912f1e3f.png) 
     88 
     89 A permutation *p* is a sequence of integers *p*1, *p*2, ..., *p**n*, consisting of *n* distinct positive integers, each of them doesn't exceed *n*. The *i*-th element of the permutation *p* is denoted as *p**i*. The size of the permutation *p* is denoted as *n*.