답안 #936370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936370	2024-03-01T17:41:26 Z	starchan	XOR (IZhO12_xor)	C++17	100 / 100	205 ms	50532 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];
	vector<int> sub;
	int chad = 0;
	void init()
	{
		C[0].pb(-1);
		C[1].pb(-1);
		sub.pb(INF);
		chad++;
		return;
	}
	void add(int x, int ind)
	{
		int curr = 0;
		sub[0] = min(sub[0], ind);
		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);
				sub.pb(INF);
			}
			curr = C[jatin][curr];
			sub[curr] = min(sub[curr], ind);
		}
		return;
	}
	int anataa(int x, int target)//is there stuff strictly greater than target?
	{
		int curr = 0;
		int val = INF;
		for(int i = LOGM-1; i >= 0; i--)
		{
			int jatin = ((x>>i)&1ll);
			int kshitij = ((target>>i)&1ll);
			if(kshitij == 0)
			{
				if(C[jatin^1][curr] != -1)
					val = min(val, sub[C[jatin^1][curr]]);
				if(C[jatin][curr] != -1)
					curr = C[jatin][curr];
				else
					return val;
			} 
			else
			{
				if(C[jatin^1][curr] == -1)
					return val;
				curr = C[jatin^1][curr];
			}
		}
		return val;
	}
};
signed main()
{
	fast();
	trie work;
	work.init();
	int n, x;
	cin >> n >> x;
	vector<int> a(n+1, 0);
	in ans = {INF, INF};
	for(int i = 1; i <= n; i++)
	{
		work.add(a[i-1], i-1);
		cin >> a[i];
		a[i]^=a[i-1];
		int r = work.anataa(a[i], x-1);//[r+1, .., i]
		ans = min(ans, {r-i, r+1});
	}
	cout << ans.s << " " << -ans.f << "\n";
	return 0;
}	

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	9 ms	1804 KB	Output is correct
6	Correct	9 ms	1996 KB	Output is correct
7	Correct	9 ms	1996 KB	Output is correct
8	Correct	10 ms	2000 KB	Output is correct
9	Correct	52 ms	22408 KB	Output is correct
10	Correct	65 ms	21384 KB	Output is correct
11	Correct	51 ms	25068 KB	Output is correct
12	Correct	61 ms	21120 KB	Output is correct
13	Correct	50 ms	21900 KB	Output is correct
14	Correct	70 ms	21384 KB	Output is correct
15	Correct	53 ms	25388 KB	Output is correct
16	Correct	52 ms	21824 KB	Output is correct
17	Correct	205 ms	45536 KB	Output is correct
18	Correct	157 ms	50532 KB	Output is correct
19	Correct	149 ms	48824 KB	Output is correct
20	Correct	174 ms	49036 KB	Output is correct