Submission #106719


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)ss << p.first<<":" << p.second<<" ";
	return ss.str();
}
 
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=1;i<=N;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 100
Code Size 2562 Byte
Status AC
Exec Time 514 ms
Memory 6016 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 22 ms 928 KB
10 AC 24 ms 804 KB
11 AC 24 ms 920 KB
12 AC 23 ms 800 KB
13 AC 45 ms 1056 KB
14 AC 52 ms 1180 KB
15 AC 57 ms 1252 KB
16 AC 228 ms 3596 KB
17 AC 160 ms 2404 KB
18 AC 508 ms 6016 KB
19 AC 21 ms 804 KB
2 AC 21 ms 680 KB
20 AC 21 ms 808 KB
21 AC 21 ms 680 KB
22 AC 21 ms 804 KB
23 AC 21 ms 928 KB
24 AC 21 ms 928 KB
25 AC 30 ms 936 KB
26 AC 25 ms 804 KB
27 AC 43 ms 1140 KB
28 AC 362 ms 4208 KB
29 AC 400 ms 4548 KB
3 AC 21 ms 800 KB
30 AC 249 ms 3156 KB
31 AC 514 ms 5668 KB
4 AC 21 ms 928 KB
5 AC 21 ms 800 KB
6 AC 21 ms 936 KB
7 AC 21 ms 936 KB
8 AC 21 ms 932 KB
9 AC 23 ms 804 KB