oj.uz

답안 #963326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963326 2024-04-14T20:52:47 Z Acanikolic XOR (IZhO12_xor) C++14
100 / 100
 108 ms 79112 KB 
#include <bits/stdc++.h>
		 		
//#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 250010;
		 
const int mod = 1e9 + 7;
		 
const int inf = 1e9;

int pref[N],a[N],trie[N * 31][2],mn[N * 31 * 2],idx = 0;

void Add(int x,int i) {
	int node = 0;
	for(int j = 30; j >= 0; j--) {
		int bit = x >> j & 1;
		if(!trie[node][bit]) trie[node][bit] = ++idx;
		node = trie[node][bit];
		mn[node] = min(mn[node],i);
	}
}

int get(int tr,int x) {
	int node = 0,val = 0,res = inf;
	for(int j = 30; j >= 0; j--) {
		int bit = x >> j & 1;
		int bt = tr >> j & 1;
		if(bit > 0) {
			if(!trie[node][bit ^ bt]) break;
			node = trie[node][bit ^ bt];
			if(!j) res = min(res,mn[node]);
		}else {
			if(trie[node][bt ^ 1] > 0) res = min(res,mn[trie[node][bt ^ 1]]);
			if(!trie[node][bt]) break;
			node = trie[node][bt];
			if(!j) res = min(res,mn[node]);
		}
	}
	return res;
}
		 		 	 		 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,x;
	cin >> n >> x;
	for(int i = 1; i < N * 31 * 2; i++) mn[i] = inf;
	int l = n + 1,r = n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = a[i] ^ pref[i - 1];
		if(pref[i] >= x) {
			l = 1,r = i;
		}
		int L = get(pref[i],x);
		//cout << L << " " << i << " " << l << " " << r << endl;
		if(i - L + 1 > r - l + 1) {
			l = L;
			r = i;
		}else if(i - L + 1 == r - l + 1 && L < l) {
			l = L;
			r = i;
		}
		Add(pref[i],i + 1);
	}
	cout << l << " " << r - l + 1;
    return 0;
}

Compilation message

xor.cpp: In function 'int get(int, int)':
xor.cpp:32:15: warning: unused variable 'val' [-Wunused-variable]
   32 |  int node = 0,val = 0,res = inf;
      |               ^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 63148 KB Output is correct
2 Correct 13 ms 63068 KB Output is correct
3 Correct 13 ms 63096 KB Output is correct
4 Correct 13 ms 63224 KB Output is correct
5 Correct 17 ms 63636 KB Output is correct
6 Correct 18 ms 63704 KB Output is correct
7 Correct 18 ms 63580 KB Output is correct
8 Correct 19 ms 63696 KB Output is correct
9 Correct 38 ms 70348 KB Output is correct
10 Correct 40 ms 70484 KB Output is correct
11 Correct 39 ms 70460 KB Output is correct
12 Correct 46 ms 70300 KB Output is correct
13 Correct 37 ms 70484 KB Output is correct
14 Correct 44 ms 70536 KB Output is correct
15 Correct 37 ms 70472 KB Output is correct
16 Correct 37 ms 70348 KB Output is correct
17 Correct 93 ms 78932 KB Output is correct
18 Correct 98 ms 79112 KB Output is correct
19 Correct 108 ms 78932 KB Output is correct
20 Correct 96 ms 79032 KB Output is correct