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
AC × 14
WA × 17
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