Submission #16888

#	Time	Username	Problem	Language	Result	Execution time	Memory
16888		erdemkiraz	XOR (IZhO12_xor)	C++98	45 / 100	536 ms	86780 KiB

xor

#   include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 250000 + 5;
const int LOG = 31;

int n, k;
int a[N];

class trie{ public:
    int id;
    trie *c[2], *dad;
    trie() {
        id = inf;
        c[0] = c[1] = dad = 0;
    }
};

typedef trie* pTrie;

pTrie root;

int add(int x, int id) {
    pTrie p = root;
    int num = 0, ans = inf;
    if(p -> c[0] or p -> c[1]) {
        for(int i = LOG - 1; i >= 0; i--) {
            bool w = x & (1 << i);
            if(p -> c[!w]) {
                num |= 1 << i;
                if(num >= k) {
                    assert(p -> c[!w] -> id and p -> c[!w] -> id != inf);
                    ans = min(ans, p -> c[!w] -> id);
                    if(p -> c[w])
                        p = p -> c[w];
                    else
                        break;
                }
                else {
                    p = p -> c[!w];
                }
            }
            else {
                p = p -> c[w];
            }
        }
    }
    p = root;
    for(int i = LOG - 1; i >= 0; i--) {
        bool w = x & (1 << i);
        if(!p -> c[w]) {
            p -> c[w] = new trie;
            p -> c[w] -> dad = p;
        }
        p = p -> c[w];
    }
    p -> id = id;
    while(p != root) {
        if(p -> c[0])
            p -> id = min(p -> id, p -> c[0] -> id);
        if(p -> c[1])
            p -> id = min(p -> id, p -> c[1] -> id);
        p = p -> dad;
    }
    return ans;
}

int main() {

    root = new trie;

    scanf("%d %d", &n, &k);

    int res = 0;

    add(0, 1);

    int ansl = inf, ansr = 0;

    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        res ^= a[i];
        int l = add(res, i + 1);
        //printf("l = %d i = %d\n", l, i);
        if(i - l > ansr - ansl) {
            ansl = l;
            ansr = i;
        }
    }

    printf("%d %d\n", ansl, ansr - ansl + 1);

    return 0;

}

• Subtask 1: 45 / 100