Submission #2438417
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T,Int X>
struct BinaryTrie{
struct Node{
bool f;
T laz;
int par,cnt,nxt[2];
Node(){}
Node(bool f,int par):
f(f),laz(0),par(par),cnt(0){nxt[0]=nxt[1]=-1;}
};
const int lim=7e6;
int idx;
vector<Node> v;
BinaryTrie():idx(0),v(lim){emplace(0,-1);}
void emplace(bool f,int par){
v[idx++]=Node(f,par);
}
void rebuild(){
vector<T> vs;
vector<int> vc;
T a=val(xmin(0));
int pos=find(a);
vs.emplace_back(a);
vc.emplace_back(v[pos].cnt);
while(val(xmax(0))!=a){
pos=next(pos);
a=val(pos);
vs.emplace_back(a);
vc.emplace_back(v[pos].cnt);
}
idx=0;
emplace(0,-1);
for(int i=0;i<(int)vs.size();i++)
for(int j=0;j<vc[i];j++) add(vs[i]);
}
inline int count(int x){
return x<0?0:v[x].cnt;
}
inline void eval(int i,int x){
if((v[x].laz>>i)&1){
swap(v[x].nxt[0],v[x].nxt[1]);
v[x].laz^=T(1)<<i;
}
for(int k=0;k<2;k++){
if(!~v[x].nxt[k]) continue;
v[v[x].nxt[k]].laz^=v[x].laz;
v[v[x].nxt[k]].f=k;
}
v[x].laz=0;
}
void add(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(b>>i)&1;
if(~v[pos].nxt[f]){
pos=v[pos].nxt[f];
continue;
}
int npos=idx;
v[pos].nxt[f]=npos;
emplace(f,pos);
pos=npos;
}
v[pos].cnt++;
for(int i=0;i<X;i++){
pos=v[pos].par;
v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
}
}
void update(const T b){
v[0].laz^=b;
}
int find(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(b>>i)&1;
if(~v[pos].nxt[f]) pos=v[pos].nxt[f];
else return -1;
}
return pos;
}
void erase(int pos){
if(pos<0) while(1);
v[pos].cnt--;
for(int i=0;i<X;i++){
pos=v[pos].par;
v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
for(int k=0;k<2;k++)
if(!count(v[pos].nxt[k])) v[pos].nxt[k]=-1;
}
}
int xmax(const T b){
int pos=0;
for(int i=X-1;i>=0;i--){
eval(i,pos);
bool f=(~b>>i)&1;
f^=!~v[pos].nxt[f];
pos=v[pos].nxt[f];
}
return pos;
}
int xmin(const T b){
return xmax(~b&((T(1)<<X)-1));
}
int next(int pos){
for(int i=-1;i<X;i++){
int par=v[pos].par;
if(v[pos].f==0&&~v[par].nxt[1])
return fmin(i,v[par].nxt[1]);
pos=par;
}
while(1);
return pos;
}
int fmin(int i,int pos){
if(i==-1) return pos;
eval(i,pos);
return fmin(i-1,v[pos].nxt[v[pos].nxt[0]==-1]);
}
T val(int pos){
if(pos<0) while(1);
T res=0;
for(int i=0;i<X;i++){
res|=T(v[pos].f)<<i;
pos=v[pos].par;
}
return res;
}
void show(){
vector<T> vs;
T a=val(xmin(0));
vs.emplace_back(a);
int pos=find(a);
while(val(xmax(0))!=a){
pos=next(pos);
a=val(pos);
vs.emplace_back(a);
}
cout<<"#######"<<endl;
for(T x:vs) cout<<x<<" ";
cout<<endl;
}
};
//END CUT HERE
//INSERT ABOVE HERE
signed JAG2013SUMMERWARMINGUP_F(){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
vector<int> s(n+1,0);
for(int i=0;i<n;i++) s[i+1]=s[i]^a[i];
map<int, int> r;
BinaryTrie<int, 30> bt;
bt.add(0);
r[bt.find(0)]=0;
int ans=-1,idx=-1,idy=-1;
for(int i=0;i<n;i++){
int k=r[bt.xmax(a[i])];
int res=s[i+1]^s[k];
if(ans<res||(ans==res&&idx>k)){
ans=res;
idx=k;
idy=i;
}
bt.update(a[i]);
bt.add(0);
if(!r.count(bt.find(0))) r[bt.find(0)]=i+1;
}
cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
return 0;
}
/*
verified on 2018/03/11
https://beta.atcoder.jp/contests/jag2013summer-warmingup/tasks/icpc2013summer_warmingUp_f
*/
signed CFR470_C(){
int n;
scanf("%d",&n);
vector<int> a(n),p(n);
for(Int i=0;i<n;i++) scanf("%d",&a[i]);
for(Int i=0;i<n;i++) scanf("%d",&p[i]);
BinaryTrie<int, 30> bt;
for(int i=0;i<n;i++) bt.add(p[i]);
for(Int i=0;i<n;i++){
if(i) printf(" ");
int k=bt.xmin(a[i]);
printf("%d",a[i]^p[k]);
bt.erase(bt.find(p[k]));
}
puts("");
return 0;
}
/*
verified on 2018/03/11
http://codeforces.com/contest/947/problem/C
*/
signed CFR477_C(){
Int n;
scanf("%lld",&n);
vector<Int> b(n);
for(Int i=0;i<n;i++) scanf("%lld",&b[i]);
BinaryTrie<Int, 60> bt;
for(Int i=0;i<n;i++) bt.add(b[i]);
Int z=0;
auto apply=[&](Int a){
z^=a;
bt.update(a);
};
vector<Int> ans;
Int x=bt.val(bt.xmin(0));
ans.emplace_back(x);
bt.erase(bt.find(x));
apply(x);
for(Int i=1;i<n;i++){
bt.add(x);
Int pos=bt.find(x);
if(bt.val(bt.xmax(0))==x){
printf("No\n");
return 0;
}
Int nxt=bt.next(pos);
Int y=bt.val(nxt);
ans.emplace_back(y^z);
bt.erase(pos);
bt.erase(nxt);
apply(x^y);
x=y;
if(bt.idx+1000>=bt.lim) bt.rebuild();
}
printf("Yes\n");
for(Int i=0;i<n;i++){
if(i) printf(" ");
printf("%lld",ans[i]);
}
printf("\n");
return 0;
}
signed main(){
//JAG2013SUMMERWARMINGUP_F();
//CFR470_C();
CFR477_C();
return 0;
}
Submission Info
Submission Time
2018-04-30 14:43:54+0900
Task
F - Maximum Segment XOR
User
beet
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
5546 Byte
Status
WA
Exec Time
74 ms
Memory
16896 KB
Compile Error
./Main.cpp: In function ‘int CFR470_C()’:
./Main.cpp:204:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:206:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(Int i=0;i<n;i++) scanf("%d",&a[i]);
^
./Main.cpp:207:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(Int i=0;i<n;i++) scanf("%d",&p[i]);
^
./Main.cpp: In function ‘int CFR477_C()’:
./Main.cpp:228:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
^
./Main.cpp:230:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attrib...
Judge Result
Set Name
All
Score / Max Score
0 / 100
Status
Set Name
Test Cases
All
1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name
Status
Exec Time
Memory
1
WA
1 ms
256 KB
10
WA
2 ms
512 KB
11
WA
2 ms
512 KB
12
WA
2 ms
384 KB
13
WA
6 ms
3456 KB
14
WA
8 ms
3456 KB
15
WA
8 ms
3968 KB
16
WA
39 ms
5504 KB
17
WA
23 ms
6912 KB
18
WA
74 ms
16896 KB
19
WA
1 ms
256 KB
2
WA
1 ms
256 KB
20
WA
1 ms
256 KB
21
WA
1 ms
256 KB
22
WA
2 ms
256 KB
23
WA
1 ms
256 KB
24
WA
2 ms
256 KB
25
WA
4 ms
768 KB
26
WA
2 ms
512 KB
27
WA
7 ms
1152 KB
28
WA
50 ms
12032 KB
29
WA
54 ms
13696 KB
3
WA
1 ms
256 KB
30
WA
36 ms
9472 KB
31
WA
72 ms
16640 KB
4
WA
1 ms
256 KB
5
WA
1 ms
256 KB
6
WA
1 ms
256 KB
7
WA
2 ms
2304 KB
8
WA
1 ms
256 KB
9
WA
2 ms
512 KB