Submission #855018

#	Time	Username	Problem	Language	Result	Execution time	Memory
855018		smirichto	XOR (IZhO12_xor)	C++17	0 / 100	1 ms	344 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 ;
int n , x ;
int a[N] ;
vector<int> v[33][2] ;

void solve() {
    cin>>n>>x ;
    for(int i = 1 ; i<=n ; i++) cin>>a[i] ;
    int ans = 0 ;
    vector<int> cnt(33 , 0) ;
    --x ;
    for(int i = 0 ; i<30 ; i++){
        v[i][0].pb(0) ;
    }
    int res = 0 ;
    for(int i = 1 ; i<=n ; i++){
        for(int bit = 0 ; bit<30 ; bit++){
            int c = ((a[i]>>bit) & 1) ;
            cnt[bit] ^= c ;
            v[bit][cnt[bit]].pb(i) ;

        }

        int l = 0 , r = i ;
        for(int bit = 30 ; bit>=0 ; bit--){
            int c = ((x>>bit) & 1) ;
            int b = (cnt[bit] ^ 1) ;
            if(c){
                auto it = lower_bound(all(v[bit][b]) , l) ;
                if(it == v[bit][b].end()) break ;
                l = *it ;
                if(l>r) break ;
                ckmin(r , v[bit][b].back()) ;
            }
            else{
                auto it = lower_bound(all(v[bit][b]) , l) ;
                if(it!= v[bit][b].end() && *it<=r){
                    int p = *it ;
                    if(ckmax(ans , i - p)) res = p ;
                }
            }
        }
    }
    cout<<res+1 << ' ' << 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: 0 / 100