Codeforces Round #399：C. Jon Snow and his Favourite Number

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:

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?

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 two integers, the maximum and the minimum strength of the rangers after performing the operation k times.

5 1 29 7 11 15 5output
13 7input
2 100000 569605 986output
986 605
http://codeforces.com/contest/768/problem/C
循环节居然是4不是2，比赛时以为是2结果被hack了
#include<stdio.h>#include<algorithm>#include<string.h>using namespace std;int a[100005], c[100005], xh[100005][2];int main(void){	int i, n, k, j, x, mn, mx, c;	scanf("%d%d%d", &n, &k, &x);	mx = -1, mn = 10005;	for(i=1;i<=n;i++)	{		scanf("%d", &a[i]);		mx = max(mx, a[i]);		mn = min(mn, a[i]);	}	c = 0, xh[0][0] = xh[0][1] = -1;	for(j=1;j<=k;j++)	{		sort(a+1, a+n+1);		mx = -1, mn = 10005;		for(i=1;i<=n;i++)		{			if(i%2)				a[i] ^= x;			mx = max(mx, a[i]);			mn = min(mn, a[i]);		}		if(j<=5)			continue;		if(mx==xh[0][0] && mn==xh[0][1] && c>2)		{			k = (k-j)%c;			printf("%d %d/n", xh[k][0], xh[k][1]);			return 0;		}		xh[c][0] = mx, xh[c++][1] = mn;	}	printf("%d %d/n", mx, mn);	return 0;}