Cod sursa(job #2271915)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 29 octombrie 2018 14:58:55
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
   
using namespace std;

typedef long long int ll;
typedef long double ld;

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

struct Trie {
    int pos;
    Trie *l, *r;

    Trie() {
        pos = -1;
        l = r = NULL;
    }
};

Trie *root = new Trie;

void Insert(Trie *node, int val, int lvl, int pos) {
    node -> pos = max(node -> pos, pos);
    if (lvl < 0) return;

    if ((1 << lvl) & val) {
        if (node -> r == NULL) node -> r = new Trie;
        Insert(node -> r, val, lvl - 1, pos);
    } else {
        if (node -> l == NULL) node -> l = new Trie;
        Insert(node -> l, val, lvl - 1, pos);
    }
}

int sofar, pos;
void Search(Trie *node, int val, int lvl, int sol) {
    if (lvl < 0) {
        sofar = sol;
        pos = node -> pos;
        return;
    }

    int num = (((1 << lvl) & val) ? 1 : 0);
    if (num == 0) {
        if(node -> r != NULL) {
            Search(node -> r, val, lvl - 1, sol + (1 << lvl));
        } else {
            Search(node -> l, val, lvl - 1, sol);
        }
    } else {
        if(node -> l != NULL) {
            Search(node -> l, val, lvl - 1, sol + (1 << lvl));
        } else {
            Search(node -> r, val, lvl - 1, sol);
        }
    }
}

int main() {
    int n; fin >> n;
    vector < int > v(n);
    for (auto &x: v) fin >> x;
    for (int i = 1; i < n; ++i) v[i] ^= v[i - 1];

    int best = -1;
    int ab, bb; ab = bb = -1;
    Insert(root, 0, 21, -1);

    if (v[0] == 0) {
        best = 0;
        ab = bb = 1;
    }
    for (int i = 0; i < n; ++i) {
        Insert(root, v[i], 21, i);
        Search(root, v[i], 21, 0);

        if (sofar == best) {
            if (bb - ab > i - pos) {
                ab = pos + 2;
                bb = i + 1;
            }
        }
        if (sofar > best) {
            best = sofar;
            ab = pos + 2;
            bb = i + 1;
        }
    }

    fout << best << " " << ab << " " << bb;
    return 0;
}