Submission #1182641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182641		hrk	XOR (IZhO12_xor)	C++17	100 / 100	253 ms	88620 KiB

xor

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define f(i,x,y) for(int i=x;i<y;i++)
#define f2(i,x,y) for(int i=x;i>=y;i--)
#define pii pair<int,int>
#define Fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int MOD =1000000007;
const int INF = 1e18;
const int N = 2e5;
struct BinaryTrie {
private:
    int B;
    struct node
    {
        int numbercount;
        node *next[2];
        int count;
        int index;
        node() {
            count = 0;
            index = INF;
            numbercount = 0;
            for (int i = 0; i < 2; i++)
                next[i] = NULL;
        }
    };
    node *root;
public:
    BinaryTrie(int b) {
        B = b;
        root = new node();
    }
    void insert(int x,int ind) {
        node* curr = root;
        curr -> count++;
        for (int i = B ; i >= 0; i--) {
            int b = x >> i & 1;
            if (curr -> next[b] == NULL) curr -> next[b] = new node();
            curr = curr -> next[b];
            curr -> count++;
            curr -> index = min(curr->index,ind);
        }
        curr->numbercount++;
    }
    void del(int x) {
        node* curr = root;
        curr -> count++;
        for (int i = B ; i >= 0; i--) {
            int b = x >> i & 1;
            if (curr -> next[b] == NULL)return;
            curr = curr -> next[b];
            curr -> count--;
        }
        curr->numbercount--;
    }
    bool search(int x) { //find if s exist
        node *curr = root;
        for (int i = B ; i >= 0; i--) {
            int b = x >> i & 1;
            if (curr->next[b] == NULL)
                return false;
            curr = curr->next[b];
        }
        return curr->numbercount > 0;
    }
    int getXorMax(int x) { // returns max ai xor s(in decimal)
        int ans = 0;
        node *curr = root;
        for (int i = B ; i >= 0; i--) {
            int b = x >> i & 1;
            if (curr->next[!b] == NULL or curr->next[!b]->count == 0) {
                curr = curr->next[b];
            }
            else {
                curr = curr->next[!b];
                ans += 1ll << i;
            }
        }
        return ans;
    }
    int getXorMin(int x) { // returns min ai xor s(in decimal)
        int ans = 0;
        node *curr = root;
        for (int i = B ; i >= 0; i--) {
            int b = x >> i & 1;
            if (curr->next[b] == NULL or curr->next[b]->count == 0) {
                curr = curr->next[!b];
                ans += 1ll << i;
            }
            else {
                curr = curr->next[b];
            }
        }
        return ans;
    }
    int query(int x, int k) { // numbers of values val ^ x < k
        int ans = 0;
        node *curr = root;
        for (int i = B ; i >= 0; i--) {
            if (curr == NULL)break;
            int b1 = x >> i & 1 , b2 = k >> i & 1;
            if (b2 == 1) {
                if (curr->next[b1])
                    ans += curr->next[b1]->count;
                curr = curr->next[!b1];
            }
            else curr = curr->next[b1];
        }
        return ans;
    }
    pii query(int x){
        node *curr = root; int ans = 0;
        for(int i=B;i>=0;i--){
            int bit = x >> i & 1;
            if(curr -> next[!bit]){
                ans += (1ll<<i);
                curr = curr->next[!bit];
            }
            else curr = curr->next[bit];
        }
        return make_pair(ans,curr->index);
    }
};
void solve(int tc){
    int n,x; cin >> n >> x;
    vector<int>v(n+1),pref(n+1);
    for(int i=1;i<=n;i++) cin >> v[i];
    for(int i=1;i<=n;i++) pref[i] = pref[i-1] ^ v[i];
    BinaryTrie T(32);
    T.insert(0,0);
    int mxlen = 0,j=n+1;
    for(int i=1;i<=n;i++){
        pii a = T.query(pref[i]);
        a.ss++;
        if(a.ff >= x){
            if(i-a.ss+1 > mxlen){
                mxlen = i-a.ss+1;
                j = a.ss;
            }
            else if(i-a.ss+1 == mxlen){
                j = min(j,a.ss);
            }
        }
        T.insert(pref[i],i);
    }
    cout << j << " " << mxlen << endl;
}
int32_t main(){

    Fast

    int t=1;

    // cin >> t;

    for(int tc=1;tc<=t;tc++){

        solve(tc);
    }
    return 0;
}

• Subtask 1: 100 / 100