Submission #16892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16892	2015-10-24T12:21:55 Z	erdemkiraz	XOR (IZhO12_xor)	C++	100 / 100	548 ms	86780 KB

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) {
                    num ^= 1 << i;
                    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 = min(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;
        }
    }

    /*
    int xl = inf, xr = 0;

    for(int i = 1; i <= n; i++) {
        int res = 0;
        for(int j = i; j <= n; j++) {
            res ^= a[j];
            if(res >= k) {
                if(j - i > xr - xl) {
                    xl = i;
                    xr = j;
                }
            }
        }
    }

    printf("%d %d\n", xl, xr - xl + 1);

    assert(xl == ansl);
    assert(xr == ansr);
    */

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

    return 0;

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2696 KB	Output is correct
2	Correct	0 ms	2696 KB	Output is correct
3	Correct	0 ms	2696 KB	Output is correct
4	Correct	1 ms	2960 KB	Output is correct
5	Correct	20 ms	4676 KB	Output is correct
6	Correct	24 ms	4940 KB	Output is correct
7	Correct	21 ms	4940 KB	Output is correct
8	Correct	25 ms	5072 KB	Output is correct
9	Correct	168 ms	42296 KB	Output is correct
10	Correct	178 ms	42428 KB	Output is correct
11	Correct	167 ms	42164 KB	Output is correct
12	Correct	188 ms	42296 KB	Output is correct
13	Correct	181 ms	42428 KB	Output is correct
14	Correct	197 ms	42428 KB	Output is correct
15	Correct	184 ms	42296 KB	Output is correct
16	Correct	169 ms	42296 KB	Output is correct
17	Correct	525 ms	86648 KB	Output is correct
18	Correct	548 ms	86780 KB	Output is correct
19	Correct	526 ms	86780 KB	Output is correct
20	Correct	514 ms	86780 KB	Output is correct