Submission #103065
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 << 21) + 10;
const int MAX_LOG_V = 21;
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[mask & (s[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 |
100 |
Code Size |
1520 Byte |
Status |
AC |
Exec Time |
118 ms |
Memory |
12580 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 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 |
53 ms |
11036 KB |
10 |
AC |
57 ms |
10988 KB |
11 |
AC |
55 ms |
11044 KB |
12 |
AC |
47 ms |
11028 KB |
13 |
AC |
52 ms |
11048 KB |
14 |
AC |
52 ms |
11168 KB |
15 |
AC |
60 ms |
11172 KB |
16 |
AC |
87 ms |
11808 KB |
17 |
AC |
75 ms |
11428 KB |
18 |
AC |
111 ms |
12580 KB |
19 |
AC |
53 ms |
11048 KB |
2 |
AC |
46 ms |
11036 KB |
20 |
AC |
52 ms |
11040 KB |
21 |
AC |
46 ms |
11052 KB |
22 |
AC |
48 ms |
10996 KB |
23 |
AC |
53 ms |
11048 KB |
24 |
AC |
53 ms |
11044 KB |
25 |
AC |
49 ms |
11052 KB |
26 |
AC |
49 ms |
11040 KB |
27 |
AC |
53 ms |
11172 KB |
28 |
AC |
94 ms |
12068 KB |
29 |
AC |
105 ms |
12204 KB |
3 |
AC |
54 ms |
11000 KB |
30 |
AC |
86 ms |
11688 KB |
31 |
AC |
118 ms |
12580 KB |
4 |
AC |
35 ms |
2784 KB |
5 |
AC |
53 ms |
11044 KB |
6 |
AC |
53 ms |
11056 KB |
7 |
AC |
53 ms |
11048 KB |
8 |
AC |
47 ms |
10996 KB |
9 |
AC |
53 ms |
11052 KB |