Submission #339169

#	Time	Username	Problem	Language	Result	Execution time	Memory
339169		scales	XOR (IZhO12_xor)	C++17	100 / 100	1379 ms	25948 KiB

xor

#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
     unordered_map<long long,long long> pos;
     cin>>n;
     cin>>w;
     vector<long long> a(n),b(n);
     cin>>a[0];
     l=n+1;
     r=-1;
     pos[a[0]]=0;
     for(i=1;i<n;i++)
     {
         cin>>x;
         a[i]=a[i-1]^x;
         pos[a[i]]=i;
         //cout<<"a[i]="<<a[i]<<endl;
     }
     maxi=0;
     for(i=0;i<n;i++)
     {
         y=w^a[i];
         r=pos[y];
         //cout<<"i="<<i<<" y="<<y<<" r="<<r<<endl;
         if(r-i>maxi || ((r-i)==maxi && i+1<viv))
         {
             maxi=r-i;
             viv=i+1;
         }
     }

     vector<long long> st(31);
     st[0]=1;
     for(i=1;i<=30;i++)
     {
         st[i]=st[i-1]*2;
     }
     dno=0;
     //cout<<"maxi="<<maxi<<endl;
     for(i=30;i>=0;i--)
     {
         z=w&st[i];
         if(z==0)
         {
             if(dno==0)
             {
                 for(j=0;j<n;j++)
                 {
                     b[j]=a[j]&st[i];
                 }
                 l=n+1;
                 r=-1;
                 for(j=0;j<n;j++)
                 {
                    if(b[j]>0)
                    {
                        l=min(l,i);
                        r=max(r,i);
                    }
                 }
                 if(r-l>maxi || ((r-l)==maxi && l+1<viv))
                 {
                    maxi=r-l;
                    viv=l+1;
                 }
             }
             else
             {
                 if(i==0)
                 {
                     //cout<<"aaaaaaaaa"<<endl;
                 }
                 pos.clear();
                 h=w+st[i];
                 h=h/st[i];
                 //cout<<"h="<<h<<endl;
                 for(j=0;j<n;j++)
                 {
                     b[j]=a[j]/st[i];
                     //cout<<"b[j]="<<b[j]<<" ";
                 }
                 //cout<<endl;
                 for(j=0;j<n;j++)
                 {
                     pos[b[j]]=j;
                 }
                 for(j=0;j<n;j++)
                 {
                     y=h^b[j];
                     r=pos[y];
                     if(r-j>maxi || ((r-l)==maxi && l+1<viv))
                     {
                        maxi=r-j;
                        viv=j+1;
                     }
                 }

             }
         }
         else
         {
             dno=1;
         }
        //cout<<"i="<<i<<" maxi="<<maxi<<endl;
     }
     cout<<viv+1<<" "<<maxi<<endl;

    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:15:17: warning: unused variable 't' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                 ^
xor.cpp:15:29: warning: unused variable 'mini' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                             ^~~~
xor.cpp:15:34: warning: unused variable 'sum' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                  ^~~
xor.cpp:15:44: warning: unused variable 'q' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                            ^
xor.cpp:15:46: warning: unused variable 'm' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                              ^
xor.cpp:15:52: warning: unused variable 'k' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                    ^
xor.cpp:15:54: warning: unused variable 'v' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                      ^
xor.cpp:15:58: warning: unused variable 'kol' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                          ^~~
xor.cpp:15:62: warning: unused variable 'x1' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                              ^~
xor.cpp:15:65: warning: unused variable 'tip' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                                 ^~~
xor.cpp:15:69: warning: unused variable 'g' [-Wunused-variable]
   15 |      long long  t,i,j,w,dno,mini,sum,x,y,z,q,m,l,r,k,v,n,kol,x1,tip,g,maxi,viv,h;
      |                                                                     ^
xor.cpp:73:46: warning: 'viv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |                  if(r-l>maxi || ((r-l)==maxi && l+1<viv))
      |                                 ~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100