답안 #531370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531370	2022-02-28T14:28:56 Z	fcw	XOR (IZhO12_xor)	C++17	100 / 100	201 ms	32436 KB

xor

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

const int K = 31;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	vector<array<int, 2>>trie(1, {-1, -1});
	vector<int>id(1, -1);
	int n, x;
	cin>>n>>x;
	vector<int>v(n+1);
	int mx = -1, ind = -1;
	int cnt = 0;
	for(int i=0;i<=n;i++){
		if(i) cin>>v[i];
		cnt ^= v[i];
		if(i){
			int cur = 0, mask = 0;
			for(int a=K;a>=0;a--){
				int b = cnt>>a&1;
				if(trie[cur][!b] == -1){
					cur = trie[cur][b];
				}
				else{
					mask |= (1<<a);
					cur = trie[cur][!b];
					if(mask >= x){
						//cout<<i+1<<" "<<mask<<" "<<id[cur]<<" "<<a<<"\n";
						if(mx < i+1 - id[cur]){
							mx = i+1 - id[cur];
							ind = id[cur];
						}
					}
				}
			}
		}
		int cur = 0;
		for(int a=K;a>=0;a--){
			int b = cnt>>a&1;
			if(trie[cur][b] == -1){
				trie[cur][b] = (int)trie.size();
				trie.push_back({-1, -1});
				id.push_back(i+1);
			}
			cur = trie[cur][b];
		}
	}
	cout<<ind<<" "<<mx<<"\n";

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	448 KB	Output is correct
5	Correct	13 ms	1312 KB	Output is correct
6	Correct	10 ms	1360 KB	Output is correct
7	Correct	11 ms	1436 KB	Output is correct
8	Correct	11 ms	1484 KB	Output is correct
9	Correct	69 ms	15516 KB	Output is correct
10	Correct	81 ms	15532 KB	Output is correct
11	Correct	73 ms	15400 KB	Output is correct
12	Correct	73 ms	15520 KB	Output is correct
13	Correct	67 ms	15436 KB	Output is correct
14	Correct	80 ms	15524 KB	Output is correct
15	Correct	84 ms	15452 KB	Output is correct
16	Correct	82 ms	15544 KB	Output is correct
17	Correct	199 ms	32400 KB	Output is correct
18	Correct	194 ms	32412 KB	Output is correct
19	Correct	201 ms	32404 KB	Output is correct
20	Correct	184 ms	32436 KB	Output is correct