Submission #3644405
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
typedef pair<int,int> P;
struct Trie{
int cnt;
int to[2];
int id;
Trie(){
}
};
int sz=1;
int qsz=0;
queue<int> que[100005];
Trie t[1<<21];
int a[100005];
int sum[100005];
void init(){
for(int i=0;i<(1<<21);i++){
t[i].cnt=0;
t[i].to[0]=-1;
t[i].to[1]=-1;
t[i].id=-1;
}
}
void add(int v,int id){
int cur=0;
for(int i=19;i>=0;i--){
t[cur].cnt++;
int b=(v>>i)&1;
// printf("add %d %d %d\n",v,i,b);
if(t[cur].to[b]==-1){
t[cur].to[b]=sz++;
}
cur=t[cur].to[b];
}
t[cur].cnt++;
if(t[cur].id==-1)t[cur].id=qsz++;
que[t[cur].id].push(id);
}
void del(int v){
int cur=0;
for(int i=19;i>=0;i--){
t[cur].cnt--;
int b=(v>>i)&1;
if(t[cur].to[b]==-1){
t[cur].to[b]=sz++;
}
cur=t[cur].to[b];
}
t[cur].cnt--;
que[t[cur].id].pop();
}
P query(int v){
int cur=0;
P ans=P(0,-1);
for(int i=19;i>=0;i--){
int b=1-((v>>i)&1);
int nxt=t[cur].to[b];
// printf("%d %d %d\n",i,b,nxt);
if(nxt==-1 || t[nxt].cnt==0){
nxt=t[cur].to[1-b];
}else{
ans.first+=(1<<i);
}
cur=nxt;
}
ans.second=que[t[cur].id].front();
return ans;
}
int main(){
int n;
scanf("%d",&n);
init();
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum[i+1]+=sum[i];
sum[i+1]^=a[i];
add(sum[i+1],i+1);
}
int ans=-1;
P p=P(0,0);
for(int i=0;i<n;i++){
P q=query(sum[i]);
if(q.first>ans){
ans=q.first;
p=P(i+1,q.second);
}
del(sum[i+1]);
}
printf("%d %d %d\n",ans,p.first,p.second);
return 0;
}
Submission Info
Submission Time
2018-11-23 17:51:55+0900
Task
F - Maximum Segment XOR
User
WAsedAC1
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2034 Byte
Status
MLE
Exec Time
135 ms
Memory
100992 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:82:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:85:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
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
MLE
66 ms
100224 KB
10
MLE
66 ms
100224 KB
11
MLE
65 ms
100224 KB
12
MLE
66 ms
100224 KB
13
MLE
69 ms
100224 KB
14
MLE
70 ms
100224 KB
15
MLE
70 ms
100224 KB
16
MLE
99 ms
100608 KB
17
MLE
84 ms
100480 KB
18
MLE
135 ms
100992 KB
19
MLE
65 ms
100224 KB
2
MLE
65 ms
100224 KB
20
MLE
65 ms
100224 KB
21
MLE
65 ms
100224 KB
22
MLE
65 ms
100224 KB
23
MLE
66 ms
100224 KB
24
MLE
65 ms
100224 KB
25
MLE
67 ms
100224 KB
26
MLE
66 ms
100224 KB
27
MLE
68 ms
100224 KB
28
MLE
109 ms
100736 KB
29
MLE
112 ms
100736 KB
3
MLE
65 ms
100224 KB
30
MLE
93 ms
100608 KB
31
MLE
128 ms
100992 KB
4
MLE
66 ms
100224 KB
5
MLE
65 ms
100224 KB
6
MLE
65 ms
100224 KB
7
MLE
65 ms
100224 KB
8
MLE
65 ms
100224 KB
9
MLE
65 ms
100224 KB