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