Submission #16887

#	Time	Username	Problem	Language	Result	Execution time	Memory
16887		erdemkiraz	XOR (IZhO12_xor)	C++98	Compilation error	0 ms	0 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] = 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(c[!w] -> id and 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;

}

Compilation message (stderr)

In file included from /usr/include/c++/4.9/cassert:43:0,
                 from /usr/include/x86_64-linux-gnu/c++/4.9/bits/stdc++.h:33,
                 from xor.cpp:1:
xor.cpp: In function ‘int add(int, int)’:
xor.cpp:42:28: error: ‘c’ was not declared in this scope
                     assert(c[!w] -> id and c[!w] -> id != inf);
                            ^
xor.cpp: In function ‘int main()’:
xor.cpp:82:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^
xor.cpp:91:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
                           ^