oj.uz

답안 #883639

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883639 2023-12-05T15:01:07 Z Requiem XOR (IZhO12_xor) C++17
100 / 100
 158 ms 39476 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define pii pair<int,int>
#define ll long long
// #define int ll
using namespace std;
 
const int N = 250000 + 5;
 
int a[N],p[N],tot = 1,child[N * 33][4],val[N * 33];
 
void upd(int k,int i){
	int cur = 1;
	for (int j = 30; j >= 0; j--){
		int b = (k & (1<<j)) > 0;
		if (!child[cur][b]){
			child[cur][b] = ++tot;
		}
		cur = child[cur][b];
		val[cur] = max(val[cur],i);
	}	
}
 
int find(int i,int mask,int lim){
	// ... == mask ^ p[i - 1]
	
	mask ^= p[i - 1];
	int cur = 1;
 
	for (int j = 30; j >= lim; j--){
		int b = (mask & (1<<j)) > 0;
		if (!child[cur][b]) return -1;
		cur = child[cur][b];
	}
 
	return val[cur] - i + 1;
}
 
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	// freopen("game.in", "r", stdin);
	// freopen("game.out", "w", stdout);
 
	int n,x;
	cin>>n>>x;
 
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i - 1] ^ a[i];
	}
 
	int ans1 = 0,ans2 = 0;
	for (int i = n; i >= 1; i--){
		upd(p[i],i);
		int res = find(i,x,0);
		if (res >= ans2) ans1 = i,ans2 = res;  
 
		int mask = 0;
		for (int j = 30; j >= 0; j--){
			if (!(x & (1<<j))){
				int res = find(i,(mask ^ (1<<j)),j);
				if (res >= ans2) ans1=i,ans2=res;  
			}
			mask ^= (x & (1<<j));
		}
	}
 
	cout<<ans1<<" "<<ans2;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 8 ms 1556 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 9 ms 1628 KB Output is correct
8 Correct 9 ms 1692 KB Output is correct
9 Correct 44 ms 17748 KB Output is correct
10 Correct 42 ms 17732 KB Output is correct
11 Correct 45 ms 17752 KB Output is correct
12 Correct 43 ms 17748 KB Output is correct
13 Correct 39 ms 17744 KB Output is correct
14 Correct 42 ms 17780 KB Output is correct
15 Correct 44 ms 17748 KB Output is correct
16 Correct 39 ms 17756 KB Output is correct
17 Correct 128 ms 37460 KB Output is correct
18 Correct 158 ms 39360 KB Output is correct
19 Correct 137 ms 39476 KB Output is correct
20 Correct 119 ms 39248 KB Output is correct