Submission #103062

---

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 & (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

Judge Result