Submission #486773

#	Time	Username	Problem	Language	Result	Execution time	Memory
486773		MilosMilutinovic	XOR (IZhO12_xor)	C++14	100 / 100	122 ms	33920 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
const int mod = 998244353;
//const int mod = 1000000007;

using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;







//Note to self: Check for overflow

//trie gas

int n,a[250005];
li xr[250005];

int mn[3729105];
int tr[3729105][2];
int br=1;

void Insert(int x,int pos)
{
    int node=0;
    bfff(i,0,30)
    {
        if (!(x&(1<<i)))
        {
            if (!tr[node][0]) tr[node][0]=++br;
            node=tr[node][0];
        }
        else
        {
            if (!tr[node][1]) tr[node][1]=++br;
            node=tr[node][1];
        }
        mn[node]=min(mn[node],pos);
    }
}

int Get(int x,int k)
{
    int node=0,res=1e9;
    bfff(i,0,30)
    {
        if (k&(1<<i))
        {
            int dr;
            if (x&(1<<i)) dr=0;
            else dr=1;
            if (!tr[node][dr]) break;
            node=tr[node][dr];
        }
        else
        {
            int dr;
            if (x&(1<<i)) dr=0;
            else dr=1;
            if (tr[node][dr])
            {
                res=min(res,mn[tr[node][dr]]);
            }
            if (!tr[node][dr^1]) break;
            node=tr[node][dr^1];
        }
    }
    return res;
}

int main()
{
    FAST;

    int n,x; cin>>n>>x;
    fff(i,1,n) cin>>a[i];
    fff(i,1,n) xr[i]=xr[i-1]^a[i];
    fff(i,0,3729105) mn[i]=1e9;

    Get(0,0);
    int ans=0,gde=0;
    //cout<<xr[n]<<"\n";
    fff(i,1,n)
    {
        int pos=Get(xr[i],x-1);
        if (ans<i-pos) ans=i-pos,gde=pos+1;
        Insert(xr[i],i);
    }
    cout<<gde<<" "<<ans<<"\n";
}

//Note to self: Check for overflow

Compilation message (stderr)

xor.cpp: In function 'void Insert(int, int)':
xor.cpp:18:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
      |                              ^
xor.cpp:58:5: note: in expansion of macro 'bfff'
   58 |     bfff(i,0,30)
      |     ^~~~
xor.cpp: In function 'int Get(int, int)':
xor.cpp:18:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
      |                              ^
xor.cpp:77:5: note: in expansion of macro 'bfff'
   77 |     bfff(i,0,30)
      |     ^~~~
xor.cpp: In function 'int main()':
xor.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
xor.cpp:108:5: note: in expansion of macro 'fff'
  108 |     fff(i,1,n) cin>>a[i];
      |     ^~~
xor.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
xor.cpp:109:5: note: in expansion of macro 'fff'
  109 |     fff(i,1,n) xr[i]=xr[i-1]^a[i];
      |     ^~~
xor.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
xor.cpp:110:5: note: in expansion of macro 'fff'
  110 |     fff(i,0,3729105) mn[i]=1e9;
      |     ^~~
xor.cpp:16:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
xor.cpp:115:5: note: in expansion of macro 'fff'
  115 |     fff(i,1,n)
      |     ^~~
xor.cpp:110:27: warning: iteration 3729105 invokes undefined behavior [-Waggressive-loop-optimizations]
  110 |     fff(i,0,3729105) mn[i]=1e9;
      |                      ~~~~~^~~~
xor.cpp:16:44: note: within this loop
   16 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                                        ~~~~^~~~~~~~~~~~
   17 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   18 | #define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   19 | #define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   20 | #define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   21 | 
      |                                             
   22 | using namespace std;
      | ~~~~~~~~~~~~~~~~~~~~                        
   23 | long double typedef ld;
      | ~~~~~~~~~~~~~~~~~~~~~~~                     
   24 | unsigned int typedef ui;
      | ~~~~~~~~~~~~~~~~~~~~~~~~                    
   25 | long long int typedef li;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~                   
   26 | pair<int,int> typedef pii;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~                  
   27 | pair<li,li> typedef pli;
      | ~~~~~~~~~~~~~~~~~~~~~~~~                    
   28 | pair<ld,ld> typedef pld;
      | ~~~~~~~~~~~~~~~~~~~~~~~~                    
   29 | vector<vector<int>> typedef graph;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
   30 | unsigned long long int typedef ull;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~         
   31 | const int mod = 998244353;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~                  
   32 | //const int mod = 1000000007;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~               
   33 | 
      |                                             
   34 | using namespace __gnu_pbds;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~                 
   35 | template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   36 | template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 | 
      |                                             
   38 | 
      |                                             
   39 | 
      |                                             
   40 | 
      |                                             
   41 | 
      |                                             
   42 | 
      |                                             
   43 | 
      |                                             
   44 | //Note to self: Check for overflow
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
   45 | 
      |                                             
   46 | //trie gas
      | ~~~~~~~~~~                                  
   47 | 
      |                                             
   48 | int n,a[250005];
      | ~~~~~~~~~~~~~~~~                            
   49 | li xr[250005];
      | ~~~~~~~~~~~~~~                              
   50 | 
      |                                             
   51 | int mn[3729105];
      | ~~~~~~~~~~~~~~~~                            
   52 | int tr[3729105][2];
      | ~~~~~~~~~~~~~~~~~~~                         
   53 | int br=1;
      | ~~~~~~~~~                                   
   54 | 
      |                                             
   55 | void Insert(int x,int pos)
      | ~~~~~~~~~~~~~~~~~~~~~~~~~~                  
   56 | {
      | ~                                           
   57 |     int node=0;
      |     ~~~~~~~~~~~                             
   58 |     bfff(i,0,30)
      |     ~~~~~~~~~~~~                            
   59 |     {
      |     ~                                       
   60 |         if (!(x&(1<<i)))
      |         ~~~~~~~~~~~~~~~~                    
   61 |         {
      |         ~                                   
   62 |             if (!tr[node][0]) tr[node][0]=++br;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   63 |             node=tr[node][0];
      |             ~~~~~~~~~~~~~~~~~               
   64 |         }
      |         ~                                   
   65 |         else
      |         ~~~~                                
   66 |         {
      |         ~                                   
   67 |             if (!tr[node][1]) tr[node][1]=++br;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   68 |             node=tr[node][1];
      |             ~~~~~~~~~~~~~~~~~               
   69 |         }
      |         ~                                   
   70 |         mn[node]=min(mn[node],pos);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~         
   71 |     }
      |     ~                                       
   72 | }
      | ~                                           
   73 | 
      |                                             
   74 | int Get(int x,int k)
      | ~~~~~~~~~~~~~~~~~~~~                        
   75 | {
      | ~                                           
   76 |     int node=0,res=1e9;
      |     ~~~~~~~~~~~~~~~~~~~                     
   77 |     bfff(i,0,30)
      |     ~~~~~~~~~~~~                            
   78 |     {
      |     ~                                       
   79 |         if (k&(1<<i))
      |         ~~~~~~~~~~~~~                       
   80 |         {
      |         ~                                   
   81 |             int dr;
      |             ~~~~~~~                         
   82 |             if (x&(1<<i)) dr=0;
      |             ~~~~~~~~~~~~~~~~~~~             
   83 |             else dr=1;
      |             ~~~~~~~~~~                      
   84 |             if (!tr[node][dr]) break;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~       
   85 |             node=tr[node][dr];
      |             ~~~~~~~~~~~~~~~~~~              
   86 |         }
      |         ~                                   
   87 |         else
      |         ~~~~                                
   88 |         {
      |         ~                                   
   89 |             int dr;
      |             ~~~~~~~                         
   90 |             if (x&(1<<i)) dr=0;
      |             ~~~~~~~~~~~~~~~~~~~             
   91 |             else dr=1;
      |             ~~~~~~~~~~                      
   92 |             if (tr[node][dr])
      |             ~~~~~~~~~~~~~~~~~               
   93 |             {
      |             ~                               
   94 |                 res=min(res,mn[tr[node][dr]]);
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   95 |             }
      |             ~                               
   96 |             if (!tr[node][dr^1]) break;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~     
   97 |             node=tr[node][dr^1];
      |             ~~~~~~~~~~~~~~~~~~~~            
   98 |         }
      |         ~                                   
   99 |     }
      |     ~                                       
  100 |     return res;
      |     ~~~~~~~~~~~                             
  101 | }
      | ~                                           
  102 | 
      |                                             
  103 | int main()
      | ~~~~~~~~~~                                  
  104 | {
      | ~                                           
  105 |     FAST;
      |     ~~~~~                                   
  106 | 
      |                                             
  107 |     int n,x; cin>>n>>x;
      |     ~~~~~~~~~~~~~~~~~~~                     
  108 |     fff(i,1,n) cin>>a[i];
      |     ~~~~~~~~~~~~~~~~~~~~~                   
  109 |     fff(i,1,n) xr[i]=xr[i-1]^a[i];
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~          
  110 |     fff(i,0,3729105) mn[i]=1e9;
      |     ~~~~~~~~~~~~~~~                         
xor.cpp:110:5: note: in expansion of macro 'fff'
  110 |     fff(i,0,3729105) mn[i]=1e9;
      |     ^~~

• Subtask 1: 100 / 100