Submission #1014615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014615		kira_zoldyck	XOR (IZhO12_xor)	C++14	100 / 100	135 ms	119764 KiB

xor

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

#define endl "\n"
#define fast ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define yes cout << "YES" << endl;
#define no cout<<"NO"<<endl;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define MP(x,y) make_pair(x,y)
#define ll long long int

typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef priority_queue<int> PQI;

const double Pii = 3.14159265358979323846;
const ll mod=                    1e9+7;
const ll mod2=                    998244353;
const ll inf=                    1e16+7;
const int mxN=(2e5 + 5e4)*30+1;
const double eps=0.00000000000000001;


ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll i,ll mod) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i,mod)) % mod) % mod;}
/*
don't start implementing until you have a solid idea and you are 90% sure of it!
----
be always fully focused, sometimes we waste time thinking about nothing!
----
when we ask more questions we have a higher probability to find our way to the solution!
----
don't give up on a problem until you have questionned all the questions you can ask urself!
(trying greedy approaches , thinking about a trick ,about using a certain data structure
a certain algorithm,opting for a certain principle (e.g: pigeon principe) , solving the opposite problem,playing with examples in order to find
a pattern, thinking backwards, and most importantly, thinking about the box!
----
when u ask a question, try to prove it either it's correct or wrong,if it's wrong or it seems
it will take us nowhere =>try another approach.
----
don't get stuck at one approach!
----
apply teleportation, if we could do this? could we solve the next task?
----
implement very carefully!
----
RE : out_of_bounds, deleting an element from an empty data_structures, dividing by zero .
----
*/


/*
order_of_key (k) : Number of items strictly smaller than k .
find_by_order(k) : K-th element in a set (counting from zero).
*/


int k;
int to[mxN][2] ,firstTraverse[mxN][2];
int nodeCount=0;
int nextNode(){
    return ++nodeCount;
}

// 0 is the root
void insert(int val,int ind){
    int currNode=0;
    for (int i = 30; i >= 0; i--) {
      int b=(val>>i)&1;
      if (to[currNode][b] == -1){
        to[currNode][b]=nextNode();
      }
      currNode=to[currNode][b];
      if(firstTraverse[currNode][b]==-1)firstTraverse[currNode][b]=ind;
    }
}

int query(int val){
    int currNode=0,mn=1e9;
    for (int i = 30; i >= 0; i--) {
      if(currNode==-1)return mn;
      int b=!((val>>i)&1);
      if (to[currNode][b] == -1){
        if((1<<i)&k)return mn;
        currNode=to[currNode][1^b];
      }else{
        if((1<<i)&k)currNode=to[currNode][b];
        else{
            mn=min(mn,firstTraverse[to[currNode][b]][b]);
            currNode=to[currNode][1^b];
        }
      }
    }
    return mn;
}



void solve(){
    int n;
    cin>>n>>k;
    k--;
    memset(firstTraverse,-1,sizeof(firstTraverse));
    memset(to,-1,sizeof(to));
    insert(0,0);
    int curr=0;
    int l=2,r=1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        curr^=x;
        int mn=query(curr);
        insert(curr,i);
        assert(mn!=-1);
        if(r-l<i-(mn+1)){
            r=i;
            l=mn+1;
        }
    }
    cout<<l<<" "<<(r-l)+1<<endl;
}



int main(){
    fast
//    freopen("cases.in","r",stdin);
//    freopen("output.txt","w",stdout);
//    cout<<fixed<<setprecision(12);
    int t=1;
//    cin>>t;
    while(t--)solve();
    return 0;
}



/*
Keeeeeeeeeep goiiiiiing gonnaaaa do it now or after it's just a matter of time inchallah
*/

• Subtask 1: 100 / 100