Cod sursa(job #3182184)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 8 decembrie 2023 18:32:53
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

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

int ind;

class Trie
{
    int lvs = 0;
    int cnt = 0;
    int indice = 0;
    Trie *next[2] = {};
public:
    void Insert(string str , int ind , int pos = 0)
    {
        if(pos < str.size())
        {
            if(!next[str[pos] - '0'])
                next[str[pos] - '0'] = new Trie;
            next[str[pos] - '0']->Insert(str , ind , pos + 1);
            if(pos == str.size() - 1)
                indice = ind;
        }
    }
    int Query (string str , int pos = 0 , int exp = 20)
    {
        if(!exp) {ind = indice;return 0;}
        int bit = str[pos] - '0';
        if(next[!bit])
            return (1 << exp) + next[!bit]->Query(str , pos + 1 , exp - 1);
        else if(next[bit])
            return next[bit]->Query(str , pos + 1 , exp - 1);
        else return 0;
    }
}trie;

int N , X , ans , S;

int main()
{
    int l , r;
    fin >> N;
    for(int i = 1; i <= N; ++i)
    {
        fin >> X;
        S ^= X;
        /// Convertesc suma in binar
        stack <string> b;
        string str = "";
        int CS = S;
        while(CS > 0)
        {
            if(CS % 2)
                b.push("1");
            else
                b.push("0");
            CS /= 2;
        }
        for(int j = 1; j <= 21 - (b.empty() ? 0 : b.size()); ++j)
            str += "0";
        while(!b.empty())
        {
            str += b.top();
            b.pop();
        }

        int t = trie.Query(str);
        if(t > ans)
            ans = t , l = ind + 1, r = i;
        trie.Insert(str , i);
    }
    fout << ans << " " << l << " " << r;
}