Submission #103058
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 = 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[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 |
282 ms |
Memory |
6048 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 |
33 ms |
6048 KB |
10 |
RE |
239 ms |
1944 KB |
11 |
RE |
234 ms |
1948 KB |
12 |
RE |
232 ms |
1708 KB |
13 |
RE |
235 ms |
1836 KB |
14 |
RE |
245 ms |
1952 KB |
15 |
RE |
236 ms |
1840 KB |
16 |
RE |
260 ms |
2600 KB |
17 |
RE |
247 ms |
2220 KB |
18 |
RE |
281 ms |
3372 KB |
19 |
AC |
30 ms |
5920 KB |
2 |
AC |
33 ms |
5916 KB |
20 |
WA |
32 ms |
5844 KB |
21 |
AC |
31 ms |
5928 KB |
22 |
RE |
237 ms |
1708 KB |
23 |
RE |
237 ms |
1808 KB |
24 |
RE |
232 ms |
1712 KB |
25 |
RE |
234 ms |
1832 KB |
26 |
RE |
240 ms |
1836 KB |
27 |
RE |
248 ms |
1976 KB |
28 |
RE |
265 ms |
2860 KB |
29 |
RE |
268 ms |
2864 KB |
3 |
AC |
31 ms |
5812 KB |
30 |
RE |
259 ms |
2476 KB |
31 |
RE |
282 ms |
3376 KB |
4 |
AC |
24 ms |
1836 KB |
5 |
RE |
246 ms |
1712 KB |
6 |
RE |
243 ms |
1820 KB |
7 |
RE |
235 ms |
1812 KB |
8 |
RE |
238 ms |
1816 KB |
9 |
RE |
235 ms |
1872 KB |