Cod sursa(job #2771008)

Utilizator Tudor_StefanaStefana Tudor Tudor_Stefana Data 24 august 2021 19:24:55
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <iostream>
using namespace std;

int n;
int a[100001];
int Max;

struct trie {
    int nr;
    int indcuv;
    trie *bin[2];
    trie () {
        nr = indcuv = 0;
        for (int i = 0; i < 2; i++)
            bin[i] = 0;
    }
};

void read() {
    int i;
    ifstream f("xormax.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i];
    f.close();
}

int biti[21];
int indstart, st, dr;

trie* root = new trie();

void insert(trie* nod, int biti[], int ind, int i) {
    if (i == -1)
        nod->indcuv = ind;
    else {
        if (nod->bin[biti[i]] == 0) {
            nod->bin[biti[i]] = new trie();
            nod->nr++;
        }
        insert(nod->bin[biti[i]], biti, ind, i - 1);
    }
}

int search(trie* nod, int biti[], int i) {
    if (i == -1) {
        indstart = nod->indcuv;
        return 0;
    }
    else {
        int inv = 1 - biti[i];
        if (nod->bin[inv] != 0)
            return (1 << i) + search(nod->bin[inv], biti, i - 1);
        else return search(nod->bin[biti[i]], biti, i - 1);
    }
    return 0;
}

void solve() {
    int i, j, sumxor = 0, x;
    Max = a[1]; st = 1, dr = 1;
    for (i = 1; i <= n; i++) {
        sumxor^= a[i];
        for (j = 0; j <= 20; j++)
            if (sumxor & (1 << j))
                biti[j] = 1;
            else biti[j] = 0;
        if (i > 1) {
            x = search(root, biti, 20);
            if (x > Max) {
                Max = x;
                st = indstart + 1;
                dr = i;
            }
        }
        insert(root, biti, i, 20);
    }
}

void output() {
    ofstream g("xormax.out");
    g << Max << ' ' << st << ' ' << dr;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}