Submission #831126

#	Time	Username	Problem	Language	Result	Execution time	Memory
831126		yeediot	XOR (IZhO12_xor)	C++14	100 / 100	208 ms	102980 KiB

xor

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=3e5*30;
int n,k;
vector<int>a;
int trie[mxn][2];
int mn[mxn];
int nxt=0;
void input(){
    cin>>n>>k;
    a.pb(0);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a.pb(x);
    }
}
void init(){
    for(int i=0;i<mxn;i++){
        mn[i]=8e18;
    }
}
vector<int>conv(int x){
    vector<int>res;
    for(int i=0;i<30;i++){
        res.pb(x>>i&1);
    }
    reverse(all(res));
    return res;
}
void insert(vector<int>vec,int p){
    int v=0;
    chmin(mn[v],p);
    for(int i=0;i<30;i++){
        if(!trie[v][vec[i]])trie[v][vec[i]]=++nxt;
        v=trie[v][vec[i]];
        chmin(mn[v],p);
    }
}
int q(vector<int>vec,int p){
    int v=0;
    int res=8e18;
    for(int i=0;i<30 and (!i or v);i++){
        int need=(k>>29-i)&1;
        int bit=vec[i];
        if(need==1)v=trie[v][1-bit];
        else{
            if(trie[v][1-bit])chmin(res,mn[trie[v][1-bit]]);
            //cout<<mn[trie[v][1-bit]]<<' ';
            v=trie[v][bit];
        }
    }
    if(v)chmin(res,mn[v]);
    //cout<<mn[v]<<' ';
    return res;
}
void solve(){
    input();
    init();
    int prefix=0;
    int ans=-8e18;
    int p=0;
    insert(conv(0),0);
    for(int i=1;i<=n;i++){
        prefix^=a[i];
        insert(conv(prefix),i);
        int x=q(conv(prefix),i);
        if(i-x>ans){
            p=x+1;
            ans=i-x;
        }
        //cout<<x<<'\n';
    }
    cout<<p<<' '<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
}
 /*
 input:
 
 */

Compilation message (stderr)

xor.cpp: In function 'long long int q(std::vector<long long int>, long long int)':
xor.cpp:56:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   56 |         int need=(k>>29-i)&1;
      |                      ~~^~

• Subtask 1: 100 / 100