Submission #891738

#	Time	Username	Problem	Language	Result	Execution time	Memory
891738		Andrey	XOR (IZhO12_xor)	C++14	100 / 100	95 ms	34348 KiB

xor

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> trie(1,{-1,-1});
vector<int> sm(1);
int x,ans = INT_MAX;

void ins(int p, int a, int d, int yo) {
    if(d == -1) {
        return;
    }
    if(a&(1 << d)) {
        if(trie[p].second == -1) {
            trie.push_back({-1,-1});
            sm.push_back(yo);
            trie[p] = {trie[p].first,trie.size()-1};
            ins(trie.size()-1,a,d-1,yo);
        }
        else {
            ins(trie[p].second,a,d-1,yo);
        }
    }
    else {
        if(trie[p].first == -1) {
            trie.push_back({-1,-1});
            sm.push_back(yo);
            trie[p] = {trie.size()-1,trie[p].second};
            ins(trie.size()-1,a,d-1,yo);
        }
        else {
            ins(trie[p].first,a,d-1,yo);
        }
    }
}

void calc(int p, int a, int d) {
    //cout << p << " " << d << " " << ans << endl;
    if(d == -1) {
        ans = min(ans,sm[p]);
        return;
    }
    if(x&(1 << d)) {
        if(a&(1 << d)) {
            if(trie[p].first == -1) {
                return;
            }
            calc(trie[p].first,a,d-1);
        }
        else {
            if(trie[p].second == -1) {
                return;
            }
            calc(trie[p].second,a,d-1);
        }
    }
    else {
        if(a&(1 << d)) {
            if(trie[p].first != -1) {
                ans = min(ans,sm[trie[p].first]);
            }
            if(trie[p].second != -1) {
                calc(trie[p].second,a,d-1);
            }
        }
        else {
            if(trie[p].second != -1) {
                ans = min(ans,sm[trie[p].second]);
            }
            if(trie[p].first != -1) {
                calc(trie[p].first,a,d-1);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,l = -1,big = 0;
    cin >> n >> x;
    vector<int> haha(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
        haha[i]^=haha[i-1];
    }
    ins(0,0,30,0);
    for(int i = 1; i <= n; i++) {
        ans = INT_MAX;
        calc(0,haha[i],30);
        if(i-ans > big) {
            big = i-ans;
            l = ans+1;
        }
        ins(0,haha[i],30,i);
    }
    cout << l << " " << big;
    return 0;
}

• Subtask 1: 100 / 100