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  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*.