Cod sursa(job #2907734)

Utilizator ana_madalina_18Radu Ana Madalina ana_madalina_18 Data 31 mai 2022 14:54:42
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
int v[100009];
string s;
class trie
{
public:
    trie *fiu[2];
    int nr=0;
    trie()
    {
        fiu[0]=nullptr;
        fiu[1]=nullptr;
    }
    void insereaza(int x, int poz_bit, int ind)
    {
        if(poz_bit>=0)
        {
            int val=(x&(1<<poz_bit));
            bool bit=0;
            if(val>0)
            {
                bit=1;
            }
            if(fiu[bit]==nullptr)
            {
                fiu[bit]=new trie();
            }
            fiu[bit]->insereaza(x,poz_bit-1,ind);
        }
        else
        {
            nr=ind;
            return;
        }
    }
    int cautare(int x, int poz_bit)
    {
        if(poz_bit>=0)
        {
            int val=(x&(1<<poz_bit));
            bool bit;
            if(val==0)
            {
                bit=1;
            }
            else
            {
                bit=0;
            }
            if(fiu[bit]!=nullptr)
            {
                return fiu[bit]->cautare(x,poz_bit-1);
            }
            else
            {
                return fiu[1-bit]->cautare(x,poz_bit-1);
            }
        }
        else
        {
            return nr;
        }
    }
};
int get_next_nr(int & poz)
{
    int numar = 0;
    while(poz<s.size() && s[poz]!=' ')
    {
        int cif = s[poz] - '0';
        numar = numar*10 + cif;
        poz++;
    }
    poz++;
    return numar;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin>>n;
    trie *radacina=new trie();
    int maxim=-1, poz_f, poz_i, poz_ini;
    radacina->insereaza(0,20,0);
    getline(fin,s);
    getline(fin,s);
    int poz=0;
    for(int i=1;i<=n;i++)
    {
        v[i] = get_next_nr(poz);
        v[i]=(v[i-1]^v[i]);
        int complementar=radacina->cautare(v[i],20);
        int rez=(v[i]^v[complementar]);
        if(rez>maxim)
        {
            maxim=rez;
            poz_ini=complementar;
            poz_f=i;
        }
        radacina->insereaza(v[i],20,i);
    }
    fout<<maxim<<' '<<poz_ini+1<<' '<<poz_f;
    return 0;
}