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