C. Jon Snow and his Favourite Number

2019-11-08 00:58:31

字体：大中小

来源：转载

供稿：网友

C. Jon Snow and his Favourite Numbertime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jon Snow now has to fight with White Walkers. He has n rangers, each of which has his own strength. Also Jon Snow has his favourite number x. Each ranger can fight with a white walker only if the strength of the white walker equals his strength. He however thinks that his rangers are weak and need to imPRove. Jon now thinks that if he takes the bitwise XOR of strengths of some of rangers with his favourite number x, he might get soldiers of high strength. So, he decided to do the following Operation k times:

Arrange all the rangers in a straight line in the order of increasing strengths.Take the bitwise XOR (is written as $\text{[math]}$ ) of the strength of each alternate ranger with x and update it's strength.Suppose, Jon has 5 rangers with strengths [9, 7, 11, 15, 5] and he performs the operation 1 time with x = 2. He first arranges them in the order of their strengths, [5, 7, 9, 11, 15]. Then he does the following:The strength of first ranger is updated to $\text{[math]}$ , i.e. 7.The strength of second ranger remains the same, i.e. 7.The strength of third ranger is updated to $\text{[math]}$ , i.e. 11.The strength of fourth ranger remains the same, i.e. 11.The strength of fifth ranger is updated to $\text{[math]}$ , i.e. 13.The new strengths of the 5 rangers are [7, 7, 11, 11, 13]

Now, Jon wants to know the maximum and minimum strength of the rangers after performing the above operations k times. He wants your help for this task. Can you help him?

Input

First line consists of three integers n, k, x (1 ≤ n ≤ 105, 0 ≤ k ≤ 105, 0 ≤ x ≤ 103) — number of rangers Jon has, the number of times Jon will carry out the operation and Jon's favourite number respectively.

Second line consists of n integers representing the strengths of the rangers a1, a2, ..., an (0 ≤ ai ≤ 103).

Output

Output two integers, the maximum and the minimum strength of the rangers after performing the operation k times.

Examplesinput

5 1 29 7 11 15 5output13 7input2 100000 569605 986output986 605思路：一开始试了一下按照当前每个位置的数不在改变的时候作为结束点。然后剩下的对2取模，来求答案，TLE在了14组。
那样的话可能就是存在循环节了，反正这么大的数据不可能是暴力跑完的。
这样也不难搞。
把每次变化的都存起来。然后得到一个新的状态的时候，先去跟之前存起来的那些状态比较，如果发现又相同的状态，那么就表示找到了循环节了。
之后求出来循环节的长度，然后取模，得到最后的答案。
#include <bits/stdc++.h>using namespace std;const int MAXN=1e5+7;int n,k,x;int cnt;struct node//用来存储已经出现过的状态{    int num[MAXN];    int MAX;    int MIN;    node()    {        MAX=0;        MIN=1e9;    }    bool operator ==(const node &a)const    {        for(int i=0; i<n; ++i)        {            if(a.num[i]!=num[i])return 0;        }        return 1;    }}p;vector<node>q;int check(){    for(int i=0; i<cnt; ++i)    {        if(q[i]==p)return i;    }    return -1;}int main(){    int i;xx:    while(~scanf("%d%d%d",&n,&k,&x))    {        q.clear();        p.MAX=0;        p.MIN=1e9;        for(i=0; i<n; ++i)        {            scanf("%d",&p.num[i]);            p.MAX=max(p.MAX,p.num[i]);            p.MIN=min(p.MIN,p.num[i]);        }        sort(p.num,p.num+n);        q.push_back(p);        cnt=0;        int pos;        while(cnt<k)        {            cnt++;            p.MAX=0;            p.MIN=1e9;            for(i=0; i<n; i+=2)            {                p.num[i]^=x;            }            for(i=0; i<n; ++i)            {                p.MAX=max(p.MAX,p.num[i]);                p.MIN=min(p.MIN,p.num[i]);            }            sort(p.num,p.num+n);            pos=check();            if(pos!=-1)//找到循环节了            {                int t=cnt-pos;//循环节长度                k=(k-pos)%t+pos;//取模之后的答案的下标                printf("%d %d/n",q[k].MAX,q[k].MIN);                goto xx;//找到了就直接重新读取下一组            }            q.push_back(p);        }        printf("%d %d/n",p.MAX,p.MIN);//表示没有找到循环节    }    return 0;}