Submission #106548


Source Code Expand

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;

//common
using i32=int;using i64=long long;using ll =i64;
#define BR "\n"

#define ALL(c) c.begin(),c.end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define EACH(it,list) for(auto it = list.begin(); it != list.end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))

//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;

//Mat
//template <typename T> using Mat = vector<vector<T>>;//H*W M*N
//template <typename T> using Mat3 = vector<Mat<T>>;

#define H(Map) Map.size()
#define W(Map) Map[0].size()

//debug
#ifdef MODE_DEBUG
#define  DUMP(x)  cerr << #x << " = "<< (x) <<endl
#define DEBUG(x) DUMP(x) << " (L" << __LINE__ << ")" << " " << __FILE__
#define CHECK(exp,act)  if(exp!=act){DUMP(exp);DEBUG(act);}
#define STOP(e)  CHECK(e);if(!(e)) exit(1);
#else
#define DUMP(x)
#define DEBUG(x)
#define CHECK(exp,act)
#define STOP(e)
#endif


//debug
template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
		//DUMP(v);
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T>>& map) {
	string res;stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)res << p.first<<":" << p.second<<" ";
	ss>>res;return res;
}

template<typename T,typename V> inline T pmod(T v,V MOD){
	int r=v%MOD;
	return r<0?r+MOD:r;
}

ll MOD =1000000007;

int main(){
	int N;cin >>N;
	vector<int> as(N);
	REP(i,N){
		int v;cin >>v;
		as[i]=v;
	}


	int mv=0;
	int l=1,r=1;
	for(int b=20;b>=0;b--){
		int v=mv|(1<<b);
		vector<int> ss(N+1);
		for(int i=1;i<N+1;i++)ss[i]=ss[i-1]^(as[i-1]>>b);
		map<int,int> hash;
		for(int i=N;i>=1;i--)	{
			hash.insert(make_pair(ss[i],i));
		}

		bool ex=false;
		for(int i=0;i<N;i++){
			if(hash.count((v>>b)^ss[i])>0){
				l=i+1;
				r=(*hash.find((v>>b)^ss[i])).second;
				ex=true;
				break;
			}
		}
		if(ex)mv=v;
	}

	cout << mv << " "<<l <<" "<<r <<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User shimomire
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2552 Byte
Status WA
Exec Time 518 ms
Memory 6232 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 25
WA × 6
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 27 ms 1080 KB
10 AC 33 ms 1056 KB
11 AC 31 ms 1152 KB
12 AC 32 ms 1056 KB
13 AC 48 ms 1440 KB
14 AC 55 ms 1472 KB
15 AC 61 ms 1468 KB
16 WA 227 ms 3888 KB
17 AC 167 ms 2684 KB
18 AC 518 ms 6232 KB
19 WA 28 ms 1056 KB
2 WA 27 ms 1064 KB
20 WA 28 ms 1080 KB
21 WA 27 ms 992 KB
22 AC 28 ms 1144 KB
23 AC 28 ms 1156 KB
24 AC 34 ms 896 KB
25 AC 32 ms 1080 KB
26 AC 26 ms 1056 KB
27 WA 42 ms 1284 KB
28 AC 350 ms 4420 KB
29 AC 404 ms 4684 KB
3 AC 23 ms 1056 KB
30 AC 241 ms 3248 KB
31 AC 493 ms 5800 KB
4 AC 25 ms 952 KB
5 AC 24 ms 952 KB
6 AC 24 ms 948 KB
7 AC 25 ms 1016 KB
8 AC 25 ms 928 KB
9 AC 26 ms 1056 KB