Cod sursa(job #3127674)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 7 mai 2023 18:10:20
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <vector>

using namespace std;

const int MAX_SIZE = 21 * 100000 + 5;

struct node {
    int chd[2] = { -1, -1 };
    int id = -1;
};

vector <node> trie(1);

void CreateNode(int nod, bool type) {
    if (trie[nod].chd[type] == -1) {
        trie[nod].chd[type] = trie.size();
        trie.emplace_back();
    }
}

void Add(int nod, int num, int bit, int id) {
    if (bit < 0) {
        trie[nod].id = id;
        return;
    }
    int val = 0;
    if ( num & ( 1 << bit ) ) {
        val = 1;
    }
    CreateNode( nod, val );
    Add(trie[nod].chd[val], num, bit - 1, id);
}

std::pair <int, int> FindOpp(int nod, int num, int bit) {
    if (bit < 0) {
        return { trie[nod].id, 0 };
    }
    int val = 0;
    if ( num & ( 1 << bit ) ) {
        val = 1;
    }
    if (trie[nod].chd[val ^ 1] != -1) {
        std::pair <int, int> sol;
        sol = FindOpp(trie[nod].chd[val ^ 1], num, bit - 1);
        sol.second |= 1 << bit;
        return sol;
    }
    else {
        std::pair <int, int> sol;
        sol = FindOpp(trie[nod].chd[val], num, bit - 1);
        return sol;
    }
}

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

    int n, i, x, val = 0;
    int pos1, pos2, max_sol = -1;
    std::pair <int, int> new_sol;
    
    fin >> n;

    Add ( 0, 0, 20, 0 );
    
    for ( i = 1; i <= n; i++ ) {
        fin >> x;
        val = val ^ x;
        new_sol = FindOpp ( 0, val, 20 );
        if ( new_sol.second > max_sol ) {
            max_sol = new_sol.second;
            pos1 = new_sol.first + 1;
            pos2 = i;
        }
        Add ( 0, val, 20, i );
    }

    fout << max_sol << " " << pos1 << " " << pos2;
}