Codeforces Round #418 (Div. 2) problem B. An express train to reveries

àì夳堔傛蜴生んèń 2022-06-14 02:43 79阅读 0赞

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

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

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 *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ *n*) — the sequence of colours in the first meteor outburst.

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.

Output

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.

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.

题目大意为，给一个n，然后输入两组n个数的数据，让你求出一组数（这组数中1-n每个数只能用一次），这组数与第一组数有且只有一个数不同，与第二组也是有且只有一个不同，而且，1,2组数据也不同。如果能有多种答案，任意一个答案输出即可。

从测试数据即可看出，有两种情况，第一种：就是第三组与第一组的数不同的下标和第三组与第二组不同的数的下标不同的时候（因为有且只有一个不同，所以可以先记录下这两个下标x,y，并把这四个数a\[x\],a\[y\],b\[x\],b\[y\]提取出来，然后再用一个C数组存除了这两个下标之外的数的出现，因为第三组与第一二组都一个不同的，那么肯定是在a\[x\],a\[y\],b\[x\],b\[y\]中的对角线即选择a\[x\],b\[y\]一组或者a\[y\],b\[x\]，并且这两个数必须是只能出现一次，判断一次就好这，第一个不行那么就是第二个。没有其他的情况。然后让这两个数顶替原来这两个下标的数，最后输出即可。

第二种：也就是第三组与第一二组的不同的数的下标一样，同上一样将其他下标的数存入C数组中，然后从1开始找哪个数没有出现过，那么这个数就是第三组这个下标位置的数，然后将这个数放入这个下标的数，输出序列数组即可。

代码也是比较简单明了哈哈哈哈哈哈~\_~

只可惜这个题昨天晚上比赛的时候没有做出来，今天看了测试数据，自己犯了一个很低级的错误。╮(╯▽╰)╭，第一次比赛就这么过去了，好伤哦-----

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[1001],b[1001],c[1001];
        int n;
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        int x,y;
        int t=1;
        x=0;
        y=0;
        for(int i=1;i<=n;i++)
        {
            if((a[i]!=b[i])&&t==1)
            {
                    x=i;
                    t=0;
                    continue;
            }
            if(a[i]!=b[i]&&t==0)
            {
                    y=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(i==x||i==y)
                continue;
            else
                c[a[i]]++;
        }
        if(y==0)
        {
            for(int i=1;i<=n;i++)
            {
                if(c[i]==0)
                {
                    a[x]=i;
                    break;
                }
            }
            for(int i=1;i<=n;i++)
            {
                if(i==1)
                printf("%d",a[i]);
                else
                printf(" %d",a[i]);
            }
        }
        else
        {
    
         c[a[x]]++;
         c[b[y]]++;
         if(c[a[x]]==1&&(c[a[x]]==c[b[y]]))
         {
             a[y]=b[y];
         }
         else
            a[x]=b[x];
         for(int i=1;i<=n;i++)
            {
                if(i==1)
                printf("%d",a[i]);
                else
                printf(" %d",a[i]);
            }
        }
        return 0;
    }

[B. An express train to reveries]: http://codeforces.com/contest/814/problem/B