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