Submission #936353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
936353	2024-03-01T16:56:50 Z	starchan	XOR (IZhO12_xor)	C++17	0 / 100	2000 ms	58036 KB

xor

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int LOGM = 32;
struct trie
{
	vector<int> C[2];
	int chad = 0;
	void init()
	{
		C[0].pb(-1);
		C[1].pb(-1);
		chad++;
		return;
	}
	void add(int x)
	{
		int curr = 0;
		for(int i = LOGM-1; i >= 0; i--)
		{
			int jatin = (x>>i)&1ll;
			if(C[jatin][curr] == -1)
			{
				C[jatin][curr] = chad++;
				C[0].pb(-1);
				C[1].pb(-1);
			}
			curr = C[jatin][curr];
		}
		return;
	}
	int anataa(int x)
	{
		int ans = 0;
		int curr = 0;
		for(int i = LOGM-1; i >= 0; i--)
		{
			int jatin = ((x>>i)&1ll);
			if(C[jatin^1][curr] != -1)
			{
				curr = C[jatin^1][curr];
				ans+=(1ll<<i);
			}
			else
				curr = C[jatin][curr];
		}
		return ans;
	}
};
signed main()
{
	fast();
	int n, x;
	cin >> n >> x;
	vector<int> a(n+1, 0);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i]^=a[i-1];
	}
	int l = 1;
	int r = n;
	while(l < r)
	{
		int val = 0;
		int m = (l+r)/2;
		trie work;
		work.init();
		work.add(a[0]);
		for(int i = m; i <= n; i++)
		{
			val = max(val, work.anataa(a[i]));
			work.add(a[i-m+1]);
		}
		if(val >= x)
			l = m+1;
		else
			r = m;
	}
	l--;
	//smallest R such that there is no i such that a[i]^a[i+R] >= x
	int X = -1;
	for(int i = 0; i <= n-l; i++)
	{
		if((a[i]^a[i+l]) >= x)
		{
			X = i+1;
			break;
		}
	}
	cout << X << " " << l << "\n";
	return 0;
}	

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	516 KB	Output is correct
4	Correct	3 ms	676 KB	Output is correct
5	Correct	64 ms	2020 KB	Output is correct
6	Correct	72 ms	2016 KB	Output is correct
7	Correct	81 ms	2112 KB	Output is correct
8	Correct	96 ms	2132 KB	Output is correct
9	Correct	763 ms	22940 KB	Output is correct
10	Correct	679 ms	22624 KB	Output is correct
11	Correct	738 ms	22952 KB	Output is correct
12	Correct	718 ms	23164 KB	Output is correct
13	Correct	746 ms	23200 KB	Output is correct
14	Correct	675 ms	23860 KB	Output is correct
15	Correct	752 ms	22956 KB	Output is correct
16	Correct	722 ms	22688 KB	Output is correct
17	Execution timed out	2039 ms	58036 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-