Cod sursa(job #2968728)

Utilizator antoniadutuDutu Antonia antoniadutu Data 21 ianuarie 2023 20:52:46
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");
int n, a, x, poz1,poz2,afs, afs1, poz1_f, poz2_f;
struct TrieNode {
    int frg;
    TrieNode *nxt[2];

    TrieNode() {
        frg = -1;

        for (int i = 0; i < 2; i++) {
            nxt[i] = NULL;
        }
    }
};

TrieNode * root = new TrieNode;

void add(TrieNode * root, int N,int pos) {
    TrieNode *curr = root;
    for(int bit = 20; bit >= 0; bit--) {
        bool now = (N & (1 << bit));

        if(curr -> nxt[now] == NULL) {
            curr -> nxt[now] = new TrieNode;
        }
        curr = curr -> nxt[now];
    }

    curr -> frg = pos;
}

void lookup(TrieNode * root, int N, int pos) {
    TrieNode *curr = root;

        afs1 = 0;
    for(int bit = 20; bit >= 0; bit--) {
        int now = (N & (1 << bit));

        now = now >> bit;

        if (curr == NULL) {
            return;
        }

        if(curr -> nxt[!now] == NULL) {;
            curr = curr -> nxt[now];
        } else {
            curr = curr -> nxt[!now];
            afs1 |= (1 << bit);
        }


        /*
        if (curr -> nxt[now] == NULL) {
            now = now ^ 1;
        }

        afs1 = afs1 + (1 << bit) * now;
        curr = curr -> nxt[now];
        */
    }

    poz1 = curr -> frg;
}

int main () {
    in >> n;

        add(root, 0, 0);
        afs = -1;
    for(int i = 1; i <= n; i++) {
        in >> a;
        x = x ^ a;

                lookup(root,x,i);

                if (afs < afs1) {
                    afs = afs1;
                    poz1_f = poz1 + 1;
                    poz2_f = i;
                }

                add(root,x,i);
    }
    out << afs << ' ' << poz1_f << ' ' << poz2_f;
    return 0;
}