814B - An express train to reveries ——暴力枚举

谁践踏了优雅 2022-06-14 03:41 133阅读 0赞

Think:  
1题意：输入两个序列，判断原始序列，原始序列与输入的两个序列最多只有1个对应元素不相等，且原始序列不会出现重复元素，序列长度2 ≤ n ≤ 1 000，元素范围1 ≤ ai ≤ n  
2思路：暴力枚举两种情况（因为原始序列不重复，且输入的序列与原始序列最多只有一个元素对应不相等，因此可以两个输入序列最多只有两个元素对应不相等，然后将未出现的至多两个元素不同顺序放进去，进而之多产生两种可能的原始序列），再判断符合对应元素不相等的个数小于等于1的条件  
3感悟：桶思想——建立数组下标与元素大小的关系

B. An express train to reveries  
time limit per test  
1 second  
memory limit per test  
256 megabytes  
input  
standard input  
output  
standard output

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.

On that night, Sengoku constructed a permutation p1, p2, …, pn 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 a1, a2, …, an and b1, b2, …, bn 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 ai ≠ bi holds.

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 ai ≠ pi, and exactly one j (1 ≤ j ≤ n) such that bj ≠ pj.

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

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.

The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ n) — the sequence of colours in the first meteor outburst.

The third line contains n space-separated integers b1, b2, …, bn (1 ≤ bi ≤ n) — the sequence of colours in the second meteor outburst. At least one i (1 ≤ i ≤ n) exists, such that ai ≠ bi holds.  
Output

Output n space-separated integers p1, p2, …, pn, denoting a possible permutation Sengoku could have had. If there are more than one possible answer, output any one of them.

Input guarantees that such permutation exists.  
Examples  
Input

5  
1 2 3 4 3  
1 2 5 4 5

Output

1 2 5 4 3

Input

5  
4 4 2 3 1  
5 4 5 3 1

Output

5 4 2 3 1

Input

4  
1 1 3 4  
1 4 3 4

Output

1 2 3 4

Note

In the first sample, both 1, 2, 5, 4, 3 and 1, 2, 3, 4, 5 are acceptable outputs.

In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int op, tp, link[4];
    
    int main(){
        int n, i, a[1004], b[1004], c[1004], d[1004];
        bool v[1004];
        while(scanf("%d", &n) != EOF){
            tp = 0;
            memset(v, false, sizeof(v));
            memset(c, -1, sizeof(c));
            for(i = 0; i < n; i++)
                scanf("%d", &a[i]);
            for(i = 0; i < n; i++){
                scanf("%d", &b[i]);
                if(a[i] == b[i] && !v[a[i]]){
                    v[a[i]] = true;
                    c[i] = d[i] = a[i];
                }
            }
            for(i = 1; i <= n; i++){
                if(!v[i]){
                    link[tp++] = i;
                }
            }
            op = 0;
            for(i = 0; i < n; i++){
                if(c[i] == -1){
                    c[i] = link[op++];
                    tp--;
                    d[i] = link[tp];
                }
            }
    
            int cnt1 = 0, cnt2 = 0;
            for(i = 0; i < n; i++){
                if(c[i] != a[i])
                    cnt1++;
                if(c[i] != b[i])
                    cnt2++;
            }
            if(cnt1 <= 1 && cnt2 <= 1){
                for(i = 0; i < n; i++)
                    printf("%d%c", c[i], i == n-1? '\n': ' ');
            }
            else {
                for(i = 0; i < n; i++)
                    printf("%d%c", d[i], i == n-1? '\n': ' ');
            }
        }
        return 0;
    }

以下为测试数据

→Judgement Protocol
    Test: #1, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 4 3
    
    1 2 5 4 5
    
    Output
    
    1 2 3 4 5
    
    Answer
    
    1 2 5 4 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #2, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    4 4 2 3 1
    
    5 4 5 3 1
    
    Output
    
    5 4 2 3 1
    
    Answer
    
    5 4 2 3 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #3, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 1 3 4
    
    1 4 3 4
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #4, time: 15 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    10
    
    1 2 3 4 7 6 7 8 9 10
    
    1 2 3 4 5 6 5 8 9 10
    
    Output
    
    1 2 3 4 5 6 7 8 9 10
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #5, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    10
    
    1 2 3 4 5 6 7 8 7 10
    
    1 2 3 4 5 6 7 8 9 9
    
    Output
    
    1 2 3 4 5 6 7 8 9 10
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #6, time: 15 ms., memory: 4 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    10
    
    1 2 3 4 5 6 7 8 4 10
    
    1 2 3 4 5 6 7 6 9 10
    
    Output
    
    1 2 3 4 5 6 7 8 9 10
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #7, time: 15 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    10
    
    8 6 1 7 9 3 5 2 10 9
    
    8 6 1 7 4 3 5 2 10 4
    
    Output
    
    8 6 1 7 4 3 5 2 10 9
    
    Answer
    
    8 6 1 7 4 3 5 2 10 9
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #8, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    10
    
    2 9 7 7 8 5 4 10 6 1
    
    2 8 7 3 8 5 4 10 6 1
    
    Output
    
    2 9 7 3 8 5 4 10 6 1
    
    Answer
    
    2 9 7 3 8 5 4 10 6 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #9, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    500
    
    346 422 445 172 378 34 209 410 119 444 279 222 65 414 228 385 386 427 75 178 243 19 27 488 127 467 94 153 162 46 379 334 238 225 301 7 234 271 68 241 406 257 483 302 419 45 329 55 300 124 203 305 282 106 442 371 129 36 183 431 166 437 76 403 50 469 404 288 58 89 370 205 407 196 52 323 110 366 37 230 353 493 214 169 457 318 413 120 207 274 314 18 66 8 486 14 485 421 461 396 310 393 272 143 328 199 57 202 104 325 480 358 471 99 111 307 236 331 446 281 268 362 336 344 324 428 47 40 48 53 286 150 273 70 3...
    
    Output
    
    346 422 445 172 378 34 209 410 119 444 279 222 65 414 228 385 386 427 75 178 243 19 27 488 127 467 94 153 162 46 379 334 238 225 301 7 234 271 68 241 406 257 483 302 419 45 329 55 300 124 203 305 282 106 442 371 129 36 183 431 166 437 76 403 50 469 404 288 58 89 370 205 407 196 52 323 110 366 37 230 353 493 214 169 457 318 413 120 207 274 314 18 66 8 486 14 485 421 461 396 310 393 272 143 328 199 57 202 104 325 480 358 471 99 111 307 236 331 446 281 268 362 336 344 324 428 47 40 48 53 286 150 273 70 327 13...
    
    Answer
    
    346 422 445 172 378 34 209 410 119 444 279 222 65 414 228 385 386 427 75 178 243 19 27 488 127 467 94 153 162 46 379 334 238 225 301 7 234 271 68 241 406 257 483 302 419 45 329 55 300 124 203 305 282 106 442 371 129 36 183 431 166 437 76 403 50 469 404 288 58 89 370 205 407 196 52 323 110 366 37 230 353 493 214 169 457 318 413 120 207 274 314 18 66 8 486 14 485 421 461 396 310 393 272 143 328 199 57 202 104 325 480 358 471 99 111 307 236 331 446 281 268 362 336 344 324 428 47 40 48 53 286 150 273 70 327 13...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #10, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    1000
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 440 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 1...
    
    Output
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155...
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #11, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    2
    
    2 2
    
    1 1
    
    Output
    
    1 2
    
    Answer
    
    1 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #12, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    1 2 2
    
    1 3 3
    
    Output
    
    1 2 3
    
    Answer
    
    1 3 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #13, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    2 2 3
    
    1 2 1
    
    Output
    
    1 2 3
    
    Answer
    
    1 2 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #14, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    1 3 3
    
    1 1 3
    
    Output
    
    1 2 3
    
    Answer
    
    1 2 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #15, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    2 1 1
    
    2 3 3
    
    Output
    
    2 1 3
    
    Answer
    
    2 3 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #16, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    3 3 2
    
    1 1 2
    
    Output
    
    1 3 2
    
    Answer
    
    1 3 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #17, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    1 3 3
    
    3 3 2
    
    Output
    
    1 3 2
    
    Answer
    
    1 3 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #18, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    3 2 3 4
    
    1 2 1 4
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #19, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    2 2 3 4
    
    1 2 3 2
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #20, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 2 4 4
    
    2 2 3 4
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #21, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    4 1 3 4
    
    2 1 3 2
    
    Output
    
    2 1 3 4
    
    Answer
    
    2 1 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #22, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    3 2 1 3
    
    4 2 1 2
    
    Output
    
    4 2 1 3
    
    Answer
    
    4 2 1 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #23, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 4 1 3
    
    2 4 1 4
    
    Output
    
    2 4 1 3
    
    Answer
    
    2 4 1 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #24, time: 0 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 3 4 4
    
    3 3 2 4
    
    Output
    
    1 3 2 4
    
    Answer
    
    1 3 2 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #25, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    100
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 41 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 28 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 ...
    
    Output
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #26, time: 15 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    997
    
    309 225 598 599 353 132 597 350 273 519 85 977 51 384 452 834 761 256 702 861 136 920 349 642 774 777 155 991 815 42 43 181 315 798 553 804 54 740 839 911 635 108 953 105 163 340 746 981 357 482 297 573 756 984 966 168 493 547 764 148 937 758 397 370 22 388 197 733 323 334 101 221 114 343 445 930 171 6 721 568 454 867 66 39 266 4 290 294 208 747 448 962 824 572 919 455 95 347 975 291 708 952 150 282 477 669 835 485 933 44 973 253 671 144 94 29 229 86 627 212 757 143 501 305 980 355 576 860 20 56 375 6...
    
    Output
    
    309 225 598 599 353 132 597 350 273 519 85 977 51 384 452 834 761 256 702 861 136 920 349 642 774 777 155 991 815 42 43 181 315 798 553 804 54 740 839 911 635 108 953 105 163 340 746 981 357 482 297 573 756 984 966 168 493 547 764 148 937 758 397 370 22 388 197 733 323 334 101 221 114 343 445 930 171 6 721 568 454 867 66 39 266 4 290 294 208 747 448 962 824 572 919 455 95 347 975 291 708 952 150 282 477 669 835 485 933 44 973 253 671 144 94 29 229 86 627 212 757 143 501 305 980 355 576 860 20 56 375 629 99...
    
    Answer
    
    309 225 598 599 353 132 597 350 273 519 85 977 51 384 452 834 761 256 702 861 136 920 349 642 774 777 155 991 815 42 43 181 315 798 553 804 54 740 839 911 635 108 953 105 163 340 746 981 357 482 297 573 756 984 966 168 493 547 764 148 937 758 397 370 22 388 197 733 323 334 101 221 114 343 445 930 171 6 721 568 454 867 66 39 266 4 290 294 208 747 448 962 824 572 919 455 95 347 975 291 708 952 150 282 477 669 835 485 933 44 973 253 671 144 94 29 229 86 627 212 757 143 501 305 980 355 576 860 20 56 375 629 99...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #27, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    1000
    
    59 615 47 121 265 619 776 404 556 783 348 417 57 440 112 152 419 293 262 110 328 973 989 273 55 41 590 267 278 523 504 921 264 239 869 756 584 162 130 336 644 697 226 257 801 194 774 968 449 297 557 574 94 12 54 181 271 933 286 979 462 207 390 133 817 992 938 35 766 488 163 704 354 323 999 447 787 459 382 374 770 638 50 806 963 46 37 623 797 9 335 742 737 127 694 617 682 845 145 477 710 380 838 715 599 446 332 236 23 405 900 641 886 100 955 942 917 344 318 512 549 312 809 892 799 169 438 319 22 637 7...
    
    Output
    
    59 615 47 121 265 619 776 404 556 783 348 417 57 440 112 152 419 293 262 110 328 973 989 273 55 41 590 267 278 523 504 921 264 239 869 756 584 162 130 336 644 697 226 257 801 194 774 968 449 297 557 574 94 12 54 181 271 933 286 979 462 207 390 133 817 992 938 35 766 488 163 704 354 323 999 447 787 459 382 374 770 638 50 806 963 46 37 623 797 9 335 742 737 127 694 617 682 845 145 477 710 380 838 715 599 446 332 236 23 405 900 641 886 100 955 942 917 344 318 512 549 312 809 892 799 169 438 319 22 637 703 176...
    
    Answer
    
    59 615 47 121 265 619 776 404 556 783 348 417 57 440 112 152 419 293 262 110 328 973 989 273 55 41 590 267 278 523 504 921 264 239 869 756 584 162 856 336 644 697 226 257 801 194 774 968 449 297 557 574 94 12 54 181 271 933 286 979 462 207 390 133 817 992 938 35 766 488 163 704 354 323 999 447 787 459 382 374 770 638 50 806 963 46 37 623 797 9 335 742 737 127 694 617 682 845 145 477 710 380 838 715 599 446 332 236 23 405 900 641 886 100 955 942 917 344 318 512 549 312 809 892 799 169 438 319 22 637 703 176...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #28, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    1000
    
    909 600 221 766 834 874 872 231 696 801 164 124 335 591 953 451 200 492 531 345 113 980 774 326 562 671 35 500 603 706 922 984 354 141 809 85 269 427 5 739 320 921 937 502 956 239 137 796 125 624 14 353 483 182 38 838 761 460 179 845 620 153 202 473 175 719 149 621 526 268 212 948 165 535 541 901 784 480 736 807 658 364 109 73 698 494 176 857 416 93 21 65 132 193 769 101 111 951 36 810 324 734 381 978 674 800 462 408 866 717 484 390 919 48 783 42 368 229 292 854 487 103 903 435 663 186 831 806 799 62...
    
    Output
    
    909 600 221 766 834 874 872 231 696 801 164 124 335 591 953 451 200 492 531 345 113 980 774 326 562 671 35 500 603 706 922 984 354 141 809 85 269 427 5 739 320 921 937 502 956 239 137 796 125 624 14 353 483 182 38 838 761 460 179 845 620 153 202 473 175 719 149 621 526 268 212 948 165 535 541 901 784 480 736 807 658 364 109 73 698 494 176 857 416 93 21 65 132 193 769 101 111 951 36 810 324 734 381 978 674 800 462 408 866 717 484 390 919 48 783 42 368 229 292 854 487 103 903 435 663 186 831 806 799 627 151 ...
    
    Answer
    
    909 600 221 766 834 874 872 231 696 801 164 124 335 591 953 451 200 492 531 345 113 980 774 326 562 671 35 500 603 706 922 984 354 141 809 85 269 427 5 739 320 921 937 502 956 239 137 796 125 624 14 353 483 182 38 838 761 460 179 845 620 153 202 473 175 719 149 621 526 268 212 948 165 535 541 901 784 480 736 807 658 364 109 73 698 494 176 857 416 93 21 65 132 193 769 101 111 951 36 810 324 734 381 978 674 800 462 408 866 717 484 390 919 48 783 42 368 229 292 854 487 103 903 435 663 186 831 806 799 627 151 ...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #29, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    1000
    
    283 699 619 182 607 82 537 768 961 778 996 737 409 19 565 636 149 526 734 359 133 845 622 876 124 903 430 726 389 958 302 797 323 501 433 914 391 708 398 798 733 879 488 61 138 74 38 589 579 80 523 203 921 902 752 599 627 472 646 675 479 759 205 327 452 163 113 727 559 812 151 179 438 94 76 159 218 881 469 566 442 392 450 500 289 528 895 468 423 412 856 612 115 519 928 624 723 195 918 401 132 255 214 328 546 314 634 202 748 108 164 816 991 22 843 147 524 735 658 63 839 720 175 847 373 506 679 199 334...
    
    Output
    
    283 699 619 182 607 82 537 768 961 778 996 737 409 19 565 636 149 526 734 359 133 845 622 876 124 903 430 726 389 958 302 797 323 501 433 914 391 708 398 798 733 879 488 61 138 74 38 589 579 80 523 203 921 902 752 599 627 472 646 675 479 759 205 327 452 163 113 727 559 812 151 179 438 94 76 159 218 881 469 566 442 392 450 500 289 528 895 468 423 412 856 612 115 519 928 624 723 195 918 401 132 255 214 328 546 314 634 202 748 108 164 816 991 22 843 147 524 735 658 63 839 720 175 847 373 506 679 199 334 907 9...
    
    Answer
    
    283 699 619 182 607 82 537 768 961 778 996 737 409 19 565 636 149 526 734 359 133 845 622 876 124 903 430 726 389 958 302 797 323 501 433 914 391 708 398 798 733 879 488 61 138 74 38 589 579 80 523 203 921 902 752 599 627 472 646 675 479 759 205 327 452 163 113 727 559 812 151 179 438 94 76 159 218 881 469 566 442 392 450 500 289 528 895 468 423 412 856 612 115 519 928 624 723 195 918 401 132 255 214 328 546 314 634 202 748 108 164 816 991 22 843 147 524 735 658 63 839 720 175 847 373 506 679 199 334 907 9...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #30, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    1000
    
    268 75 593 697 195 401 434 279 256 65 81 156 599 917 186 761 154 381 445 961 879 353 386 522 193 868 705 228 24 260 990 801 592 105 874 382 887 533 209 722 505 764 366 143 510 614 810 281 72 74 735 13 146 122 20 934 376 803 663 31 259 875 113 941 90 174 600 563 559 134 2 394 757 189 598 607 685 144 246 965 306 59 739 866 940 704 527 954 98 88 474 861 988 102 254 579 83 571 18 512 613 759 730 876 891 771 28 983 955 914 203 909 245 286 267 395 804 417 257 942 756 633 199 556 499 283 87 403 995 750 464 ...
    
    Output
    
    268 75 593 697 195 401 434 279 256 65 81 156 599 917 186 761 154 381 445 961 879 353 386 522 193 868 705 228 24 260 990 801 592 105 874 382 887 533 209 722 505 764 366 143 510 614 810 281 72 74 735 13 146 122 20 934 376 803 663 31 259 875 113 941 90 174 600 563 559 134 2 394 757 189 598 607 685 144 246 965 306 59 739 866 940 704 527 954 98 88 474 861 988 102 254 579 83 571 18 512 613 759 730 876 891 771 28 983 955 914 203 909 245 286 267 395 804 417 257 942 756 633 199 556 499 283 87 403 995 750 464 160 89...
    
    Answer
    
    268 75 593 697 195 401 434 279 256 65 81 156 599 917 186 761 154 381 445 961 879 353 386 522 193 868 705 228 24 260 990 801 592 105 874 382 887 533 209 722 505 764 366 143 510 614 810 281 72 74 735 13 146 122 20 934 376 803 663 31 259 875 113 941 90 174 600 563 559 134 2 394 757 189 598 607 685 144 246 965 306 59 739 866 940 704 527 954 98 88 474 861 988 102 254 579 83 571 18 512 613 759 730 876 891 771 28 983 955 914 203 909 245 286 267 395 804 417 257 942 756 633 199 556 499 283 87 403 995 750 464 160 89...
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #31, time: 0 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    5 4 5 3 1
    
    4 4 2 3 1
    
    Output
    
    5 4 2 3 1
    
    Answer
    
    5 4 2 3 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #32, time: 15 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    4 1 2 4 5
    
    3 1 2 5 5
    
    Output
    
    3 1 2 4 5
    
    Answer
    
    3 1 2 4 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #33, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    2 2 3
    
    1 3 3
    
    Output
    
    1 2 3
    
    Answer
    
    1 2 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #34, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    1 1 3
    
    2 3 3
    
    Output
    
    2 1 3
    
    Answer
    
    2 1 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #35, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    5 4 5 3 1
    
    2 4 4 3 1
    
    Output
    
    2 4 5 3 1
    
    Answer
    
    2 4 5 3 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #36, time: 15 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    3
    
    3 3 1
    
    2 1 1
    
    Output
    
    2 3 1
    
    Answer
    
    2 3 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #37, time: 15 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    5 4 3 5 2
    
    5 4 1 1 2
    
    Output
    
    5 4 3 1 2
    
    Answer
    
    5 4 3 1 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #38, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    6
    
    1 2 3 4 2 5
    
    1 6 3 4 4 5
    
    Output
    
    1 6 3 4 2 5
    
    Answer
    
    1 6 3 4 2 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #39, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 3 2 1
    
    2 3 2 1
    
    Output
    
    4 3 2 1
    
    Answer
    
    4 3 2 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #40, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 3 3 4
    
    1 4 3 4
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #41, time: 0 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    11
    
    1 2 3 4 5 6 7 8 9 10 10
    
    1 2 3 4 5 6 7 8 9 10 3
    
    Output
    
    1 2 3 4 5 6 7 8 9 10 11
    
    Answer
    
    1 2 3 4 5 6 7 8 9 10 11
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #42, time: 15 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 2 5
    
    1 4 3 3 5
    
    Output
    
    1 4 3 2 5
    
    Answer
    
    1 4 3 2 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #43, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 4 3
    
    1 2 5 4 2
    
    Output
    
    1 2 5 4 3
    
    Answer
    
    1 2 5 4 3
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #44, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 4 4
    
    1 2 3 4 3
    
    Output
    
    1 2 3 4 5
    
    Answer
    
    1 2 3 4 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #45, time: 0 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 3 1 4
    
    1 3 4 4
    
    Output
    
    1 3 2 4
    
    Answer
    
    1 3 2 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #46, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    2 5 3 2 1
    
    4 5 3 3 1
    
    Output
    
    4 5 3 2 1
    
    Answer
    
    4 5 3 2 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #47, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 2 5
    
    1 3 3 4 5
    
    Output
    
    1 2 3 4 5
    
    Answer
    
    1 2 3 4 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #48, time: 15 ms., memory: 20 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    5 2 3 4 5
    
    2 2 3 4 5
    
    Output
    
    1 2 3 4 5
    
    Answer
    
    1 2 3 4 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #49, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    5 4 1 1 2
    
    5 4 3 5 2
    
    Output
    
    5 4 3 1 2
    
    Answer
    
    5 4 3 1 2
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #50, time: 0 ms., memory: 8 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 4 3 4
    
    1 3 3 4
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #51, time: 15 ms., memory: 12 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    1 2 3 1
    
    1 2 3 2
    
    Output
    
    1 2 3 4
    
    Answer
    
    1 2 3 4
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #52, time: 0 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    4 5 3 3 1
    
    2 5 3 2 1
    
    Output
    
    4 5 3 2 1
    
    Answer
    
    4 5 3 2 1
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #53, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    5
    
    1 2 3 5 5
    
    1 2 3 4 3
    
    Output
    
    1 2 3 4 5
    
    Answer
    
    1 2 3 4 5
    
    Checker Log
    
    ok Correct ^ ^
    
    Test: #54, time: 15 ms., memory: 16 KB, exit code: 0, checker exit code: 0, verdict: OK
    Input
    
    4
    
    2 3 3 4
    
    2 4 3 4
    
    Output
    
    2 1 3 4
    
    Answer
    
    2 1 3 4
    
    Checker Log
    
    ok Correct ^ ^