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
AC × 31
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