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
) of the strength of each alternate ranger with x and update it's strength.
- The strength of first ranger is updated to
, i.e. 7. - The strength of second ranger remains the same, i.e. 7.
- The strength of third ranger is updated to
, i.e. 11. - The strength of fourth ranger remains the same, i.e. 11.
- The strength of fifth ranger is updated to
, i.e. 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?
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 2 9 7 11 15 5
13 7
2 100000 569 605 986
986 605
解题思路：
根据题意，其肯定会有循环节，先模拟，然后判断一下其是否到某一次时，其最大最小值达到稳定
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define cinq ios::sync_with_stdio(false)
#define pb push_back
#define mp make_pair
//#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 1e7+5;
typedef struct node{
int x;
int index;
}NODE;
void initt()
{
}
int maxx[100005];
int minn[100005];
int n,k,x,t;
vector<int> a;
int main()
{
int tt;
cinq;
cin >>n>>k>>x;
for(int i=0;i<n;i++)
{
cin>>tt;
a.push_back(tt);
}
// cout << mm<<nn<<endl;
sort(a.begin(),a.end());
maxx[0] = a[n-1];
minn[0] = a[0];
for(int i=1;i<=k;i++)
{
sort(a.begin(),a.end());
maxx[i] = a[n-1];
minn[i] = a[0];
if(i>=3)
{
if(maxx[i]==maxx[i-1]&&minn[i]==minn[i-1]&&
maxx[i]==maxx[i-2]&&minn[i]==minn[i-2]&&
maxx[i]==maxx[i-3]&&minn[i]==minn[i-3])
{
cout << a[n-1]<<" "<<a[0]<<endl;
return 0;
}
}
for(int j=0;j<a.size();j+=2)
{
a[j] ^= x;
}
}
sort(a.begin(),a.end());
cout << a[n-1]<<" "<<a[0]<<endl;
return 0;
}