Submission #855026

#	Time	Username	Problem	Language	Result	Execution time	Memory
855026		smirichto	XOR (IZhO12_xor)	C++17	100 / 100	101 ms	158352 KiB

xor

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pi pair<ll,ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define clean(v) (v).resize(distance((v).begin(), unique(all(v))));
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define mod mod
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;

void io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

template<class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

template<class T>
bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }

void nop() {
    cout << -1 << endl;
    return;
}

const int N = (3e5+5)*33 + 5 ;
int n , x ;
int a[N] ;
int to[N][2] , mn[N][2] ;

int ndcnt = 0 ;
int nxt(){
    return ++ndcnt ;
}
void insert(int x , int pos)
{
    int t = 0 ;
    for(int bit = 30 ; bit>=0 ; bit--){
        int c = (x>>bit) & 1 ;
        if(to[t][c] == -1) to[t][c] = nxt() ;
        ckmin(mn[t][c] , pos) ;
        t = to[t][c] ;
    }

}

int query(int val , int x)
{
    int ret = 1e9 ;
    int t = 0 ;
    for(int bit = 30 ; bit>=0 ; bit--){
        if(t==-1) break ;
        int c = (val>>bit) & 1 , cx = (x>>bit) & 1 ;
        if(cx){
            t = to[t][c^1] ;
        }
        else{
            ckmin(ret , mn[t][c^1]) ;
            t = to[t][c] ;
        }
    }
    return ret ;
}

void solve() {
    cin>>n>>x ;
    for(int i = 0 ; i<N ; i++){
        for(int j = 0 ; j<2 ; j++){
            to[i][j] = -1 ;
            mn[i][j] = 1e9 ;
        }
    }
    int ans = 0 , idx = 0 ;
    insert(0 , 0) ;
    for(int i = 1 ; i<=n ; i++){
        cin>>a[i] , a[i] ^= a[i-1] ;
        int res = query(a[i] , x-1) ;
        if(ckmax(ans , i - res)) idx = res+1 ;
        insert(a[i] ,  i) ;
    }
    cout<<idx<<' '<<ans<<endl;


}

int main() {
//#ifndef ONLINE_JUDGE
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
//#endif
    io();
    ll tt = 1;
    //cin>>tt ;
    while (tt--) {
        solve();
    }

    return 0;
}

• Subtask 1: 100 / 100