Submission #3882367


Source Code Expand

     #include <bits/stdc++.h>

//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-10)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x,y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
/*
                                            class Point{
                                            	public:
                                            	double x,y;
                                            	Point(double x=0,double y=0):x(x),y(y) {}
                                            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                            	Point operator * (double a) {return Point(x*a,y*a);}
                                            	Point operator / (double a) {return Point(x/a,y/a);}
                                            	double absv() {return sqrt(norm());}
                                            	double norm() {return x*x+y*y;}
                                            	bool operator < (const Point &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const Point &p) const{
                                            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                            	}
                                            };
                                            typedef Point Vector;
                                     #define pl pair<int,pas>
                                            struct Segment{
                                            Point p1,p2;
                                            };
                                             double dot(Vector a,Vector b){
                                            	return a.x*b.x+a.y*b.y;
                                            }
                                            double cross(Vector a,Vector b){
                                            	return a.x*b.y-a.y*b.x;
                                            }
                                        
                bool parareru(Point a,Point b,Point c,Point d){
                //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
                	return abs(cross(a-b,d-c))<EPS;
                }
                double distance_ls_p(Point a, Point b, Point c) {
                  if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
                  if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
                  return abs(cross(b-a, c-a)) / (b-a).absv();
                }
                bool is_intersected_ls(Segment a,Segment b) {
                	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
                	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
                //		cout<<"sss"<<endl;
                		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
                		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
                		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
                		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
                		return false;
                	}
                  else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
                }
                 
                double segment_dis(Segment a,Segment b){
                	if(is_intersected_ls(a,b))return 0;
                	double r=distance_ls_p(a.p1, a.p2, b.p1);
                	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
                	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
                	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
                	return r;
                }
                Point intersection_ls(Segment a, Segment b) {
                  Point ba = b.p2-b.p1;
                  double d1 = abs(cross(ba, a.p1-b.p1));
                  double d2 = abs(cross(ba, a.p2-b.p1));
                  double t = d1 / (d1 + d2);
                 
                  return a.p1 + (a.p2-a.p1) * t;
                }
 */                
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                                double distans(double x1,double y1,double x2,double y2){
                                	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                                	return sqrt(rr);
                                	
                                }
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
    
                                
                int pr[1000010];
                int inv[1000010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
    double bekid(double w,int r){
    	if(r==0) return 1.0;
    	if(r==1) return w;
    	if(r%2) return bekid(w,r-1)*w;
    	double f=bekid(w,r/2);
    	return f*f;
    }
                
    			int comb(int nn,int rr){
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
                
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                	for(int i=0;i<ert;i++) inv[i]=beki(pr[i],mod-2,mod);
                	
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
    
                                     //----------------kokomade tenpure------------

// hightがdの頂点から生える子は数のdビット目を見る。葉のhightは-1
// root のhightは最大ビット数。dビット目が絶対0ならdでおk
typedef struct trie{
	
	int hight;
	int num;
	trie* child[2];
}trie;


trie* newtrie(int hight,int num){
	trie* TR=new trie;
	TR->hight=hight;
	TR->num=num;
	TR->child[0]=NULL;
	TR->child[1]=NULL;
	return TR;
}

void add_num(trie* root,int val){
	trie* node_now=root;
	while(1){
		node_now->num++;
		if(node_now->hight==-1)break;
		int next_bit=((val>>(node_now->hight))&1ll);
		if(node_now->child[next_bit]==NULL){
			node_now->child[next_bit]=newtrie(node_now->hight-1,0);
		}
		node_now=node_now->child[next_bit];
		
	}
	return;
}
vector<int>pos[1<<20];
int exist_num(trie* root, int val){//valがいくつ入っているか
	trie* node_now=root;
	while(1){
		if(node_now->num==0) return false;
		if(node_now->hight==-1)return node_now->num;
		int next_bit=((val>>(node_now->hight))&1ll);
		if(node_now->child[next_bit]==NULL){
			return 0;
		}
		node_now=node_now->child[next_bit];
	}
}

void delete_num(trie* root,int val,int kesukosuu=-1){
	int kesu;
	if(kesukosuu==-1) kesu=exist_num(root,val);
	else kesu=kesukosuu;
	if(kesu==0)return;
	pos[val].pop_back();
	trie* node_now=root;
	while(1){
		node_now->num-=kesu;
		if(node_now->hight==-1){
			return;
		}
		int next_bit=((val>>(node_now->hight))&1ll);
		if(node_now->child[next_bit]==NULL){
			cout<<"!!!!!! no such key!!"<<endl;
			assert(0);
		}
		node_now=node_now->child[next_bit];
	}
}

int tugi(trie* root, int val){
	trie* node_now=root;
	int ans=0;
	while(1){
		if(node_now->hight==-1)return ans;
		int next_bit=1^((val>>(node_now->hight))&1ll);
		if(node_now->child[next_bit]==NULL){
			ans+=(1ll<<node_now->hight)*(1-next_bit);
			node_now=node_now->child[1-next_bit];
		}
		else if(node_now->child[next_bit]->num==0){
			ans+=(1ll<<node_now->hight)*(1-next_bit);
			node_now=node_now->child[1-next_bit];
		}
		else{
				ans+=(1ll<<node_now->hight)*(next_bit);
			node_now=node_now->child[next_bit];
		}
	}
}
int a[100020]={};


 signed main(){

    	       cin.tie(0);
   			ios::sync_with_stdio(false);
 int n;
 	cin>>n;
 	for(int i=1;i<=n;i++){
 		int y;
 		cin>>y;
 		a[i]=(a[i-1]^y);
 	//	cout<<a[i]<<endl;
 	}
 	for(int i=n;i>=1;i--)pos[a[i]].pb(i);
 	trie* root=newtrie(22,0);
 	for(int i=1;i<=n;i++)add_num(root,a[i]);
 //cout<<"d"<<endl;
 	pa3 ans={inf,inf,inf};
 	for(int i=1;i<=n;i++){
 		int ima=a[i-1];
 		int d=tugi(root,ima);
 	//	cout<<d<<endl;
 					ans=min(ans,{-(d^a[i-1]),i,pos[d].back()});
 		delete_num(root,a[i],1);
 	}
 	cout<<-ans.x<<" "<<ans.y<<" "<<ans.z<<endl;
 	
 	return 0;
  }

Submission Info

Submission Time
Task F - Maximum Segment XOR
User smiken
Language C++14 (GCC 5.4.1)
Score 100
Code Size 14857 Byte
Status AC
Exec Time 154 ms
Memory 51200 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 11 ms 26112 KB
10 AC 12 ms 26496 KB
11 AC 11 ms 26496 KB
12 AC 11 ms 26368 KB
13 AC 18 ms 28672 KB
14 AC 19 ms 29056 KB
15 AC 20 ms 29696 KB
16 AC 73 ms 37248 KB
17 AC 48 ms 36352 KB
18 AC 154 ms 51200 KB
19 AC 10 ms 26112 KB
2 AC 11 ms 26112 KB
20 AC 10 ms 26112 KB
21 AC 10 ms 26112 KB
22 AC 11 ms 26112 KB
23 AC 10 ms 26112 KB
24 AC 11 ms 26112 KB
25 AC 13 ms 26752 KB
26 AC 11 ms 26496 KB
27 AC 16 ms 27264 KB
28 AC 90 ms 41600 KB
29 AC 113 ms 42880 KB
3 AC 11 ms 26112 KB
30 AC 64 ms 37376 KB
31 AC 133 ms 44544 KB
4 AC 10 ms 26112 KB
5 AC 10 ms 26112 KB
6 AC 10 ms 26112 KB
7 AC 11 ms 26112 KB
8 AC 10 ms 26112 KB
9 AC 11 ms 26368 KB