Cod sursa(job #3348416)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 21 martie 2026 17:20:57
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <map>

using namespace std;
const int NMAX = 100000;

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

struct trie{ ///exista sau nu doar la niv 21
    trie *zero;
    trie* unu;
    trie() {
        zero = NULL;
        unu = NULL;
    }
};
void add(trie* start, int nr, int bit) { ///bit sunt FIII
    if(bit == -1)
        return;
    //cout << "suntem la " << (nr & (1 << bit)) << " la bitul " << bit << '\n';
    if(nr & (1 << bit)) { ///unu
        if(start->unu == NULL)
            start->unu = new trie();
        add(start->unu, nr, bit - 1);
    }
    else {
        if(start->zero == NULL)
            start->zero = new trie();
        add(start->zero, nr, bit - 1);
    }
}

int ans = 0;
void findd(trie* start, int nr, int bit) {
    if(bit == -1) ///am terminat
        return;
    // cout << ans << " ";
    // cout << "suntem la " << (nr & (1 << bit)) << " la bitul " << bit << '\n';
    if(nr & (1 << bit)) { ///incercam sa gasim fara
        if(start->zero == NULL) { ///nu exista, nasol
            ans ^= (1 << bit);
            findd(start->unu, nr, bit - 1);
        }
        else
            findd(start->zero, nr, bit - 1);
    }
    else { ///incercam sa cautam cu
        if(start->unu == NULL) {
            //cout << "nu avem\n";
            findd(start->zero, nr, bit - 1);
        }
        else {
            ans ^= (1 << bit);
            //cout << "avem\n";
            findd(start->unu, nr, bit - 1);
        }
    }
}

int v[NMAX + 2];
map <int, int> umap; ///pt xor-uri
int main() {
    trie *radacina = new trie();
    int n;
    cin >> n;
    add(radacina, 0, 20); ///20 de biti actually
    umap[0] = 0;
    // ans = 1;
    // findd(radacina, 1, 20);
    // cout << ans;
    // return 0;

    int maxx = -1, st, dr;
    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        v[i] = (v[i - 1] ^ a);
        // cout << v[i] << " ";

        ans = v[i];
        findd(radacina, v[i], 20);
        // cout << ans << '\n';
        if(ans > maxx) {
            maxx = ans;
            ans ^= v[i]; ///ca sa ii gasim partenerul
            st = umap[ans] + 1;
            dr = i;
        }
        // break;


        if(umap.find(v[i]) == umap.end()) ///nici sa nu adaugam de mai multe ori
            add(radacina, v[i], 20);
        umap[v[i]] = i;
    }
    /*for(auto var : umap) {
        cout << var.first << " " << var.second << '\n';
    }*/
    cout << maxx << " " << st << " " << dr;
    return 0;
}