Cod sursa(job #3298759)

Utilizator mateilucaLuca Matei Gabriel mateiluca Data 1 iunie 2025 13:44:58
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int k, mini, l, indice, a[100005];
int prefix;
int lung, biti[33];
vector<int> v[10005];
struct Nod{
    int cnt, nr_fii, nr_ordine, poz;
    Nod *fiu[30];
    Nod()
    {
        cnt = nr_fii = 0;
        nr_ordine = ++k;
        poz = -1;
        memset(fiu, 0, sizeof(fiu));
    }
};
class Trie{
public:
    Nod *head;
    Trie()
    {
        head = new Nod;
    }
    void Insert_litere(Nod *nod, char *s)
    {
        if(*s == '\0')
        {
            nod->cnt++;
            return ;
        }
        if(nod->fiu[*s - 'a'] == 0)
        {
            Nod *nod2 = new Nod;
            nod->fiu[*s - 'a'] = nod2;
            nod->nr_fii++;
            v[indice].push_back(k);
        }
        else v[indice].push_back(nod->fiu[*s - 'a']->nr_ordine);
        Insert_litere(nod->fiu[*s - 'a'], s + 1);
    }

    int Delete(Nod *nod, char *s)
    {
        if(*s == '\0')
            nod->cnt--;
        else if(Delete(nod->fiu[*s - 'a'], s + 1))
        {
            nod->nr_fii--;
            nod->fiu[*s - 'a'] = 0;
        }
        if(nod->cnt == 0 && nod->nr_fii == 0 && nod != head)
        {
            delete nod;
            return 1;
        }
        return 0;
    }

    int Query(Nod *nod, char *s)
    {
        if(*s == '\0')
            return nod->cnt;
        if(nod->fiu[*s - 'a'] == 0)
            return 0;
        return Query(nod->fiu[*s - 'a'], s + 1);
    }

    int Prefix(Nod *nod, char *s, int sol)
    {
        if(*s == '\0')
            return sol;
        if(nod->fiu[*s - 'a'] == 0)
            return sol;
        return Prefix(nod->fiu[*s - 'a'], s + 1, sol + 1);
    }

    bool Prefix_comun(int x)
    {
        for(int i = 2;i <= l;i++)
            if(v[a[i]][x - 1] != v[a[1]][x - 1])
                return 0;
        return 1;
    }

    int Grad_de_asemanare()
    {
        int st, dr, mij;
        st = 1;dr = mini;
        while(st <= dr)
        {
            mij = (st + dr) / 2;
            if(Prefix_comun(mij))
                st = mij + 1;
            else dr = mij - 1;
        }
        return dr;
    }

    void Insert_prefix_sum(Nod *nod, int ind, int pas)
    {
        if(ind == lung + 1)
        {
            nod->poz = pas;
            return ;
        }
        if(nod->fiu[biti[ind]] == 0)
        {
            Nod *nod2 = new Nod;
            nod->fiu[biti[ind]] = nod2;
        }
        Insert_prefix_sum(nod->fiu[biti[ind]], ind + 1, pas);
    }

    pair<int, int> Find_the_best_XOR(Nod *nod, int bit, int nr, int scad)
    {
        int i, bit_1, bit_2;
        bit_1 = bit_2 = -1;
        for(i = bit;i >= 0 && bit_1 == -1;i--)
            if(nod->fiu[i] && !((1 << i) & prefix)) bit_1 = i;
            else if(nod->fiu[i]) bit_2 = i;
        if(bit_1 > -1)
            return Find_the_best_XOR(nod->fiu[bit_1], bit_1 - 1, nr + (1 << bit_1), scad);
        if(bit_2 > -1 && bit_1 == -1)
        {
            if(nod->poz > -1)
                return {nr + prefix - scad, nod->poz};
            return Find_the_best_XOR(nod->fiu[bit_2], bit_2 - 1, nr, scad + (1 << bit_2));
        }
        return {nr + prefix - scad, nod->poz};
    }

};

int main()
{
    Trie T;
    /// Problema Trie(Arhiva educationala)
    /**
    int op;
    char ch[25];
    while(fin >> op >> ch)
    {
        switch(op)
        {
            case 0: T.Insert_litere(T.head, ch);break;
            case 1: T.Delete(T.head, ch);break;
            case 2: fout << T.Query(T.head, ch) << "\n";break;
            case 3: fout << T.Prefix(T.head, ch, 0) << "\n";break;
        }
    }
    */

    /// Problema ratina(infoarena, ONI 2006)
    /**
    int n, m, i, j;
    char ch[2005];
    string s[10005];
    fin >> n >> m;
    for(i = 1;i <= n;i++)
    {
        fin >> s[i];
        for(j = 0;s[i][j] != 0;j++)
            ch[j] = s[i][j];
        ch[j] = 0;
        indice = i;
        T.Insert_litere(T.head, ch);
    }
    while(m)
    {
        fin >> l;
        mini = 2000;
        for(i = 1;i <= l;i++)
        {
            fin >> a[i];
            if(mini > s[a[i]].length())
                mini = s[a[i]].length();
        }
        fout << T.Grad_de_asemanare() << "\n";
        m--;
    }
    */

    ///Problema xormax(infoarena)
    int n, i, j, sol, start, finish;
    pair<int, int> maxi;
    fin >> n;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    sol = -1;prefix = 0;
    for(i = 1;i <= n;i++)
    {
        prefix ^= a[i];
        lung = 0;
        for(j = 20;j >= 0;j--)
            if(prefix & (1 << j))
                biti[++lung] = j;
        maxi = T.Find_the_best_XOR(T.head, 20, 0, 0);
        if(maxi.first > sol && maxi.second > -1)
        {
            sol = maxi.first;
            finish = i;
            start = maxi.second + 1;
        }
        if(prefix > sol)
        {
            sol = prefix;
            finish = i;
            start = 1;
        }
        T.Insert_prefix_sum(T.head, 1, i);
    }
    fout << sol << " " << start << " " << finish << "\n";
    fout.close();
    return 0;
}