# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
87408 | wzy | XOR (IZhO12_xor) | C++11 | 3 ms | 376 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ll long long
struct node{
int bt , ist , idrmq = 1000000;
node *f[2];
};
node * trie;
void insert(int cbit, int vl , int idx, node*& root){
if(cbit < 0){
root->idrmq = min(idx , root->idrmq);
root->ist = 1;
root->bt = cbit;
return ;
}
bool t = (((1<<cbit) & vl) ? 1 : 0);
if(root->f[t]){
insert(cbit-1 , vl , idx , root->f[t]);
}
else{
root->f[t] = new node();
root->f[t]->bt = cbit - 1;
insert(cbit-1 , vl , idx , root->f[t]);
}
if(root->f[0]) root->idrmq = min(root->idrmq , root->f[0]->idrmq);
if(root->f[1]) root->idrmq = min(root->idrmq, root->f[1]->idrmq);
}
int query(int vl , int cbit, bool mt , int X , node * root){
if(vl == 4){
}
if(cbit < 0){
return root->idrmq;
}
if(mt){
if(1<<cbit & X){
if(root->f[1]) return query(vl , cbit-1 , mt , X , root->f[1]);
else return 1000000;
}
else{
int Pl = 10000000;
if(root->f[1]) Pl =query(vl , cbit-1 , 0 , X , root->f[1]);
else if(root->f[0]) Pl = min(Pl , query(vl, cbit-1, 1,X , root->f[0]));
return Pl;
}
}
else{
return root->idrmq;
}
}
int n , x;
int V[250005];
struct ans{
int id , k;
bool operator<(const ans X){
if(X.k == k){
return id > X.id;
}
return k < X.k;
}
} ;
int32_t main(){
scanf("%d%d" , &n , &x);
trie = new node();
ans curr;
curr.k = -1;
for(int i = 1 ; i <= n; i ++){
scanf("%d" , &V[i]);
V[i] ^= V[i-1];
insert(30 , V[i] , i ,trie);
int U = query(V[i] , 30 , 1 , x ,trie );
//cout<<V[i] << " " << U<<" " << i << endl;
ans P = {U , i - U + 1};
if(curr < P) curr = P;
}
printf("%d %d\n" , curr.id , curr.k);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |