Cod sursa(job #3145705)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 16 august 2023 18:36:23
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <string.h>
using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

#define NMAX 100005

int n;
int v[NMAX], aux[25];
int maxim = -1, l, r;

struct trie {
    int poz;
    trie *v[2];
    trie() {
        poz = 0;
        memset(v, 0, sizeof(v));
    }
} *Q;

void query(int poz) {
    memset(aux, 0, sizeof(aux));
    int x = v[poz];
    for (int k = 0; k <= 21; ++k) {
        aux[21 - k] = x % 2;
        x /= 2;
    }
    trie *j = Q;
    int sum = 0;
    for (int i = 0; i <= 21; ++i) {
        if (j->v[(aux[i] ^ 1)] != 0) {
            sum += (1 << (21 - i));
            j = j->v[(aux[i] ^ 1)];
        } else {
            j = j->v[(aux[i])];
        }
    }
    if (sum > maxim) {
        maxim = sum;
        l = j->poz + 1;
        r = poz;
        if (l == 0) {
            l = 1;
        }
        if (r == 0) {
            r = 1;
        }
        if (r < l) {
            r = l;
        }
    }
}

void update(int poz) {
    memset(aux, 0, sizeof(aux));
    int x = v[poz];
    for (int k = 0; k <= 21; ++k) {
        aux[21 - k] = x % 2;
        x /= 2;
    }
    trie *j = Q;
    for (int i = 0; i <= 21; ++i) {
        if (j->v[(aux[i])] != 0) {
            j = j->v[(aux[i])];
        } else {
            j->v[(aux[i])] = new trie;
            j = j->v[(aux[i])];
        }
    }
    j->poz = poz;
}

int main() {
    Q = new trie;
    update(0);

    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];

        v[i] ^= v[i - 1];
        query(i);
        update(i);
    }

    fout << maxim << ' ' << l << ' ' << r;
    return 0;
}