Submission #30833

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30833	2017-07-27T10:24:13 Z	Kerim	XOR (IZhO12_xor)	C++14	100 / 100	276 ms	90888 KB

xor

#include "bits/stdc++.h"
#define MAXN 250009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int LOGN=30;
int par[MAXN],tree[MAXN*LOGN][2],node,sub[MAXN*LOGN],n,k;
void upd(int x){
	int now=0;
	for(int i=29;i>=0;i--){
		int bit=par[x]>>i&1;
		if(!tree[now][bit])
			tree[now][bit]=++node;
		now=tree[now][bit];
		umax(sub[now],x);	
	}
}
int get(int x){
	int now=0,val=0,res=0;
	for(int i=29;i>=0;i--){
		int bit=x>>i&1;
		int v1=tree[now][bit^1];
		int v0=tree[now][bit];
		if(v0 and v1){
			if(val+(1<<i)>=k)
				umax(res,sub[v1]),now=v0;
			else
				val+=(1<<i),now=v1;
		}
		else if(v1){
			if(val+(1<<i)>=k)
				umax(res,sub[v1]);
			else
				val+=(1<<i);
			now=v1;
		}
		else
			now=v0;
	}
	return res;
}
int main(){
	//~ #ifndef ONLINE_JUDGE
    //~ freopen("file.in", "r", stdin);
	//~ #endif	
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		par[i]=par[i-1]^x;
	}int ans,mx=0;
	for(int i=n;i>=1;i--){
		upd(i);int res=get(par[i-1]);
		if(res and res-i+1>=mx)
			mx=res-i+1,ans=i;
	}
	printf("%d %d\n",ans,mx);
	return 0;
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
xor.cpp:63:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	90888 KB	Output is correct
2	Correct	0 ms	90888 KB	Output is correct
3	Correct	3 ms	90888 KB	Output is correct
4	Correct	0 ms	90888 KB	Output is correct
5	Correct	9 ms	90888 KB	Output is correct
6	Correct	9 ms	90888 KB	Output is correct
7	Correct	13 ms	90888 KB	Output is correct
8	Correct	19 ms	90888 KB	Output is correct
9	Correct	69 ms	90888 KB	Output is correct
10	Correct	83 ms	90888 KB	Output is correct
11	Correct	83 ms	90888 KB	Output is correct
12	Correct	89 ms	90888 KB	Output is correct
13	Correct	66 ms	90888 KB	Output is correct
14	Correct	99 ms	90888 KB	Output is correct
15	Correct	99 ms	90888 KB	Output is correct
16	Correct	96 ms	90888 KB	Output is correct
17	Correct	263 ms	90888 KB	Output is correct
18	Correct	273 ms	90888 KB	Output is correct
19	Correct	263 ms	90888 KB	Output is correct
20	Correct	276 ms	90888 KB	Output is correct