Cod sursa(job #1509427)

Utilizator lflorin29Florin Laiu lflorin29 Data 23 octombrie 2015 20:47:54
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

struct paft {
    int wh;
    paft *st, *dr;

    paft() {
        wh = 0;
        st = dr = 0;
    }
};

void Relax (const bool &value, paft* &T1) {
    if (!value) {
        if (!T1->st)
           T1->st = new paft;
        T1 = T1->st;
    }
    else {
        if (!T1->dr)
            T1->dr = new paft;
        T1 = T1->dr;
    }
}

void add (int value, int whpos, paft* T1) {
    for (int i = 21; i >= 0; --i)
        Relax(value & (1 << i), T1);
    T1->wh = whpos;
}

int qq (int value, paft* T1) {
    for (int i = 21; i >= 0 ; --i) {
        bool b1 = value & (1 << i);
        if (b1) {
           if (T1->st)
              T1 = T1->st;
            else T1 = T1->dr;
        }
        else {
            if (T1->dr)
              T1 = T1->dr;
             else T1 = T1->st;
        }
    }
    return T1->wh;
}

int main() {
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");

    int N;
    cin >> N;
    vector <int> A(N);

    for (int i = 0; i < N; ++i)
        cin >> A[i];
    paft* T = new paft;
    add(A[0], 0, T);

    int x1 = 0, y1 = 0, val1 = A[0];
    for (int i = 1; i < N; ++i) {
        A[i] ^= A[i - 1];
        int prostucn = qq(A[i], T), valp = A[i] ^ A[prostucn];
        if (valp > val1) {
           val1 = valp;
           x1 = prostucn;
           y1 = i;
        }
        add(A[i], i, T);
    }
    cout << val1 << ' ' << x1 + 2 << ' ' << y1 + 1;
    return 0;
}