Submission #168533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
168533	2019-12-13T13:30:14 Z	abil	XOR (IZhO12_xor)	C++14	100 / 100	288 ms	66936 KB

xor

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_bacak
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

struct str{
	int nol, bir, pr, pos;
	str(){
		pos = INF;
		nol = bir = pr = 0;
	}
};

int a[N], pr[N], cnt = 1, X;
str t[N * 4];

void add(int x,int pos){
	int v = 1;
	for(int i = 30;i >= 0; i--){
		int f = (x & (1 << i));
		int p = v;
		if(f){
			if(!t[v].bir){
				t[v].bir = ++cnt;
			}
			v = t[v].bir;
		} 
		else{
			if(!t[v].nol){
				t[v].nol = ++cnt;
			}
			v = t[v].nol;
		}
		t[v].pr = p;
	}
	t[v].pos = min(t[v].pos, pos);
	while(t[v].pr){
		x = v;
		v = t[v].pr;
		t[v].pos = min(t[v].pos, t[x].pos);
	}
}

int get(int x){
	int res = INF;
	int v = 1;
	for(int i = 30;i >= 0; i--){
		int f = (x & (1 << i));
		if(X & (1 << i)){
			if(!f){
				v = t[v].bir;
			}
			else{
				v = t[v].nol;
			}
		}
		else{
			if(f){
				res = min(res, t[t[v].nol].pos);
				v = t[v].bir;
			}
			else{
				res = min(res, t[t[v].bir].pos);
				v = t[v].nol;
			}
		}
	}
	res = min(res, t[v].pos);
	return res;
}
main()
{
	int n;
	scanf("%d%d", &n, &X);
	for(int i = 1;i <= n; i++){
		scanf("%d", &a[i]);
		pr[i] = pr[i - 1] ^ a[i];
	}
	pair<int,int > ans;
	ans = {0,0};
	add(0, 0);
	for(int i = 1;i <= n; i++){
		int pos = get(pr[i]);
		int len = i - pos;
		if(len > ans.fr){
			ans.fr = len;
			ans.sc = pos + 1;
		}
		add(pr[i], i);
	}
	cout << ans.sc << " " << ans.fr;
}
/*
011
111
101
1
*/

Compilation message

xor.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
xor.cpp: In function 'int main()':
xor.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &X);
  ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	63096 KB	Output is correct
2	Correct	56 ms	62968 KB	Output is correct
3	Correct	56 ms	62968 KB	Output is correct
4	Correct	56 ms	62968 KB	Output is correct
5	Correct	69 ms	63352 KB	Output is correct
6	Correct	72 ms	63352 KB	Output is correct
7	Correct	73 ms	63352 KB	Output is correct
8	Correct	76 ms	63480 KB	Output is correct
9	Correct	133 ms	64504 KB	Output is correct
10	Correct	135 ms	64504 KB	Output is correct
11	Correct	138 ms	64632 KB	Output is correct
12	Correct	136 ms	64568 KB	Output is correct
13	Correct	138 ms	64648 KB	Output is correct
14	Correct	134 ms	64504 KB	Output is correct
15	Correct	136 ms	64504 KB	Output is correct
16	Correct	133 ms	64476 KB	Output is correct
17	Correct	277 ms	66812 KB	Output is correct
18	Correct	281 ms	66808 KB	Output is correct
19	Correct	288 ms	66936 KB	Output is correct
20	Correct	277 ms	66892 KB	Output is correct