Submission #571414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571414	2022-06-02T07:26:24 Z	BackNoob	XOR (IZhO12_xor)	C++14	100 / 100	197 ms	60424 KB

xor

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 24211007;
const ll infll = 1e18 + 7;
const int base = 200;
const int LOG = 29;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct Node{
	Node* child[2];
	int minpos;
	Node()
	{
		child[0] = child[1] = NULL;
		minpos = inf;
	}
};

Node* root = new Node();

void add(int x, int idx)
{
	Node* p = root;
	for(int i = 29; i >= 0; i--) {
		int nxt = BIT(x, i);
		if(p -> child[nxt] == NULL) 
			p -> child[nxt] = new Node();
		p = p -> child[nxt];
		minimize(p -> minpos, idx); 
	}
}

int n;
int k;
int a[mxN];
int pre[mxN];
int timer = 0;
pair<int, int> ans = {-1, -1};

int calc(int x)
{
	// if(timer == 3) cout << x << endl;
	int res = inf;
	Node* p = root;
	for(int j = LOG; j >= 0; j--) {
		if(x & (1 << j)) {
			if(!(k & (1 << j))) {
				if(p -> child[0] != NULL)
					minimize(res, p -> child[0] -> minpos);
				if(p -> child[1] == NULL) return res;
				p = p -> child[1];
				// cout << 1;
			}
			else {
				if(p -> child[0] == NULL) return res;
				p = p -> child[0];
				// cout << 0;
			}
		}
		else {
			if(k & (1 << j)) {
				if(p -> child[1] == NULL) return res;
				p = p -> child[1];
				// cout << 1;
			}
			else {
				if(p -> child[1] != NULL) 
					minimize(res, p -> child[1] -> minpos);
				if(p -> child[0] == NULL) return res;
				p = p -> child[0];
				// cout << 0;
			}
		}
	}
	minimize(res, p -> minpos);

	return res;
}


void solve()
{	
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];

	for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ a[i];

	add(pre[0], 0);

		
	for(int i = 1; i <= n; i++) {
		++timer;
		int x = calc(pre[i]);
		// cout << endl;
		if(x != inf) {
			if((ans.se - ans.fi + 1) < i - x + 1) {
				ans.fi = x;
				ans.se = i;
			}
			if((ans.se - ans.fi + 1) == i - x + 1) {
				if(ans.fi > x) {
					ans.fi = x;
					ans.se = i;
				}
			}
		}
		add(pre[i], i);
	}

	cout << ans.fi + 1 << ' ' << (ans.se - ans.fi - 1 + 1);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
		
    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	7 ms	2004 KB	Output is correct
6	Correct	10 ms	2264 KB	Output is correct
7	Correct	8 ms	2260 KB	Output is correct
8	Correct	8 ms	2380 KB	Output is correct
9	Correct	58 ms	28236 KB	Output is correct
10	Correct	63 ms	28488 KB	Output is correct
11	Correct	59 ms	28244 KB	Output is correct
12	Correct	59 ms	28364 KB	Output is correct
13	Correct	66 ms	28400 KB	Output is correct
14	Correct	66 ms	28404 KB	Output is correct
15	Correct	57 ms	28360 KB	Output is correct
16	Correct	64 ms	28292 KB	Output is correct
17	Correct	185 ms	60296 KB	Output is correct
18	Correct	161 ms	60424 KB	Output is correct
19	Correct	197 ms	60408 KB	Output is correct
20	Correct	179 ms	60420 KB	Output is correct