Submission #446571

#	Time	Username	Problem	Language	Result	Execution time	Memory
446571		minaie_mehrzad	XOR (IZhO12_xor)	C++14	100 / 100	492 ms	153796 KiB

xor

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

const int maxn = 25e4 + 10, lg = 31;
int n, a[maxn], z;

struct node {
    node *rc, *lc;
    int mn;
    
    node () {
        lc = nullptr;
        rc = nullptr;
        mn = 1e9;
    }
    
    node * getChild(int x) {
        if (x) {
            if (rc == nullptr) rc = new node();
            return rc;
        } else {
            if (lc == nullptr) lc = new node();
            return lc;
        }
    }
};

struct Trie {
    node *root;
    
    Trie () {
        root = new node();
    }
    
    void add(int x, int y) {
        node * cur = root;
        for (int i = lg; i >= 0; i--) {
            cur = cur->getChild(!!((1 << i) & x));
            cur->mn = min(cur->mn, y);
        }
    }
} T;

int solve(int x) {
    int ans = 1e9;
    node *cur = T.root;
    
    for (int i = lg; i >= 0; i--) {
        int c = !!((1 << i) & x), d = !!((1 << i) & z);
        
        if (!d) {
            ans = min(ans, cur->getChild(!c)->mn);
        }
        
        cur = cur->getChild(c ^ d);
    }
    
    ans = min(ans, cur->mn);
    return ans;
}

int main () {
    ios_base::sync_with_stdio(false);
    
    cin >> n >> z;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i-1];
        T.add(a[i], i);
    }
    
    int ans = 0, ind = 0;
    
    for (int i = 1; i <= n; i++) {
        if (a[i] >= z && ans < i) {
            ans = i;
            ind = 1;
        }
        
        int r = solve(a[i]);

        if (ans < i - r) {
            ans = i - r;
            ind = r + 1;
        }
    }
    
    cout << ind << " " << ans;
    
    return 0;
}

• Subtask 1: 100 / 100