codeforces-scrape

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

814B.md (2891B)


      1 Source: https://codeforces.com/problemset/problem/814/B
      2 
      3 B. An express train to reveries
      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 Sengoku still remembers the mysterious "colourful meteoroids" she discovered with Lala-chan when they were little. In particular, one of the nights impressed her deeply, giving her the illusion that all her fancies would be realized.
     22 
     23 On that night, Sengoku constructed a permutation *p*1, *p*2, ..., *p**n* of integers from 1 to *n* inclusive, with each integer representing a colour, wishing for the colours to see in the coming meteor outburst. Two incredible outbursts then arrived, each with *n* meteorids, colours of which being integer sequences *a*1, *a*2, ..., *a**n* and *b*1, *b*2, ..., *b**n* respectively. Meteoroids' colours were also between 1 and *n* inclusive, and the two sequences were not identical, that is, at least one *i* (1 ≤ *i* ≤ *n*) exists, such that *a**i* ≠ *b**i* holds.
     24 
     25 Well, she almost had it all — each of the sequences *a* and *b* matched exactly *n* - 1 elements in Sengoku's permutation. In other words, there is exactly one *i* (1 ≤ *i* ≤ *n*) such that *a**i* ≠ *p**i*, and exactly one *j* (1 ≤ *j* ≤ *n*) such that *b**j* ≠ *p**j*.
     26 
     27 For now, Sengoku is able to recover the actual colour sequences *a* and *b* through astronomical records, but her wishes have been long forgotten. You are to reconstruct any possible permutation Sengoku could have had on that night.
     28 
     29 Input
     30 
     31 The first line of input contains a positive integer *n* (2 ≤ *n* ≤ 1 000) — the length of Sengoku's permutation, being the length of both meteor outbursts at the same time.
     32 
     33 The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ *n*) — the sequence of colours in the first meteor outburst.
     34 
     35 The third line contains *n* space-separated integers *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ *n*) — the sequence of colours in the second meteor outburst. At least one *i* (1 ≤ *i* ≤ *n*) exists, such that *a**i* ≠ *b**i* holds.
     36 
     37 Output
     38 
     39 Output *n* space-separated integers *p*1, *p*2, ..., *p**n*, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.
     40 
     41 Input guarantees that such permutation exists.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 5  
     49 1 2 3 4 3  
     50 1 2 5 4 5
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 1 2 5 4 3
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 5  
     63 4 4 2 3 1  
     64 5 4 5 3 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 5 4 2 3 1
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 4  
     77 1 1 3 4  
     78 1 4 3 4
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 1 2 3 4
     85 ```
     86 
     87 Note
     88 
     89 In the first sample, both 1, 2, 5, 4, 3 and 1, 2, 3, 4, 5 are acceptable outputs.
     90 
     91 In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.