Submission #168533

#	Time	Username	Problem	Language	Result	Execution time	Memory
168533		abil	XOR (IZhO12_xor)	C++14	100 / 100	288 ms	66936 KiB

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 (stderr)

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 / 100