Submission #1359004

#TimeUsernameProblemLanguageResultExecution timeMemory
1359004bakhtiyarnXOR (IZhO12_xor)C++20
0 / 100
0 ms580 KiB
#include "bits/stdc++.h"
using namespace std;
#define int long long

const int N = 3e5+5;
int a[N];

struct Trie {
    int C;
    vector<int> l, r, mn;
    void fill(int n){
        l.assign(n*60, 0);
        r.assign(n*60, 0);
        C = 1;
        mn.assign(n*60, 1e9);
    }

    void add(int i, int x){
        int u = 0;
        for(int b=30; b>=0; b--){
            bool is = (1ll<<b)&x;

            if(!is){
                if(!l[u]) l[u] = C++;
                u = l[u];
            } else {
                if(!r[u]) r[u] = C++;
                u = r[u];
            }

            mn[u] = min(mn[u], i);
        }
    }

    int query(int u, int x, int k, int b, int you, bool fir){
        if(!u and !fir) return 1e9;
        if(b < 0) return 1e9;
        bool is1 = (1ll<<b)&x;
        bool is2 = (1ll<<b)&k;

        if(is1){
            if(is2) return query(l[u], x, k, b-1, you, false);
            return min(mn[l[u]], query(r[u], x, k, b-1, you+(1ll<<b), false));
        } else {
            if(is2) return query(r[u], x, k, b-1, you+(1ll<<b), false);
            return min(mn[r[u]], query(l[u], x, k, b-1, you, false));
        }
    }
};

void solve(){
    int n, x; cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> a[i], a[i] ^= a[i-1];
    
    Trie T; T.fill(n);

    T.add(0, 0);

    array<int, 2> ans = {1, 1};

    for(int i=1; i<=n; i++) {
        T.add(i, a[i]);
        int l = T.query(0, a[i], x, 30, 0, true);
        ans = max(ans, {i-l, (-l-1)});
    }
    cout << -ans[1] << " " << ans[0] << '\n';
}  

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // #ifndef ONLINE_JUDGE
    // freopen("input", "r", stdin);
    // freopen("output", "w", stdout);
    // #endif

    solve();
}
#Result Execution timeMemoryGrader output
Fetching results...