# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
333855 | limabeans | XOR (IZhO12_xor) | C++17 | 1 ms | 364 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 1e6 + 5;
struct node {
node *ch[2];
int mx;
node() {
ch[0]=ch[1]=NULL;
mx=0;
}
};
node *trie;
int n,x;
int a[maxn];
void insert(int idx, int val) {
node *at = trie;
for (int i=29; i>=0; i--) {
at->mx = max(at->mx, idx);
if (at->ch[val>>i&1] == NULL) {
at->ch[val>>i&1] = new node();
}
at = at->ch[val>>i&1];
}
at->mx = max(at->mx, idx);
}
int dfs(node *at, int i, int suf, bool higher=false) {
if (at == NULL) {
return -1;
}
if (i==-1) {
if (!higher) return -1;
return at->mx;
}
int hi = -1;
for (int b=0; b<2; b++) {
if (higher || ((suf>>i&1)^b) >= (x>>i&1)) {
hi = max(hi, dfs(at->ch[b], i-1, suf, higher || ((suf>>i&1)^b) > (x>>i&1)));
}
}
return hi;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
trie = new node();
cin>>n>>x;
for (int i=0; i<n; i++) {
cin>>a[i];
}
int suffix = 0;
insert(n, suffix);
int ansi = -1;
int anslen = -1;
for (int i=n-1; i>=0; i--) {
suffix ^= a[i];
int to = dfs(trie, 29, suffix, false);
if (to-i >= anslen) {
ansi = i;
anslen = to-i;
}
insert(i, suffix);
}
cout<<ansi+1<<" "<<anslen<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |