Submission #103054
Source Code Expand
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, n) for(int i = (n) - 1; i >= (a); i--)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define fst first
#define snd second
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 110000;
const int MAX_V = (1 << 20) + 10;
const int MAX_LOG_V = 20;
int n;
ll a[MAX_N], s[MAX_N];
int pos[MAX_V];
bool exist[MAX_V];
void solve(){
int v = 0;
int mask = 0;
RREP(i, MAX_LOG_V){
memset(exist, false, sizeof(exist));
mask |= (1 << i);
REP(j, n + 1){
exist[s[j] & mask] = true;
}
bool ok = false;
REP(j, n + 1){
if(exist[a[j] ^ (v | (1 << i))]){
ok = true;
break;
}
}
if(ok) v |= (1 << i);
}
if(v == 0){
cout << 0 << ' ' << 1 << ' ' << 1 << endl;
return;
}
memset(pos, -1, sizeof(pos));
REP(i, n + 1){
if(pos[s[i]] == -1 || pos[s[i]] > i){
pos[s[i]] = i;
}
}
pii p = pii(-1, -1);
REP(i, n + 1){
int ti = i;
int tj = pos[v ^ s[i]];
if(tj == -1) continue;
if(ti > tj) swap(ti, tj);
pii q = pii(ti, tj);
if(p.fst == -1 || p > q){
p = q;
}
}
cout << v << ' ' << p.fst + 1 << ' ' << p.snd << endl;
return;
}
int main(){
cin >> n;
REP(i, n){
cin >> a[i];
s[i + 1] = s[i] ^ a[i];
}
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Maximum Segment XOR |
User |
torimal |
Language |
C++ (GCC 4.4.7) |
Score |
0 |
Code Size |
1509 Byte |
Status |
WA |
Exec Time |
110 ms |
Memory |
7464 KB |
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 |
AC |
37 ms |
5896 KB |
10 |
WA |
35 ms |
5928 KB |
11 |
WA |
34 ms |
5932 KB |
12 |
WA |
34 ms |
5928 KB |
13 |
AC |
38 ms |
5932 KB |
14 |
AC |
40 ms |
5928 KB |
15 |
AC |
41 ms |
6044 KB |
16 |
AC |
69 ms |
6688 KB |
17 |
AC |
56 ms |
6304 KB |
18 |
AC |
110 ms |
7464 KB |
19 |
AC |
34 ms |
5928 KB |
2 |
AC |
34 ms |
5924 KB |
20 |
WA |
37 ms |
5880 KB |
21 |
AC |
36 ms |
5928 KB |
22 |
WA |
36 ms |
5928 KB |
23 |
WA |
33 ms |
5920 KB |
24 |
WA |
34 ms |
5932 KB |
25 |
WA |
36 ms |
5928 KB |
26 |
WA |
34 ms |
5928 KB |
27 |
WA |
38 ms |
6052 KB |
28 |
WA |
80 ms |
6956 KB |
29 |
WA |
88 ms |
7076 KB |
3 |
AC |
37 ms |
5924 KB |
30 |
WA |
70 ms |
6568 KB |
31 |
WA |
99 ms |
7464 KB |
4 |
AC |
29 ms |
1828 KB |
5 |
AC |
33 ms |
5880 KB |
6 |
WA |
37 ms |
5924 KB |
7 |
WA |
36 ms |
5920 KB |
8 |
AC |
36 ms |
5932 KB |
9 |
WA |
37 ms |
5936 KB |