Cod sursa(job #2985181)

Utilizator LXGALXGA a LXGA Data 25 februarie 2023 20:05:46
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#define ll long long
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int n, s[100001], pos;
struct trie
{
    vector<int> cnt;
    trie* next[2];
    trie()
    {
        next[0] = nullptr;
        next[1] = nullptr;
    }
    void insert(int nr,int p)
    {
        if (p == 0)
            cnt.push_back(pos);
        else
        {
            int ok = 0;
            if (nr & p)
                ok = 1;
            if (next[ok] == nullptr)
                next[ok] = new trie;
            next[ok]->insert(nr, p / 2);
        }
    }
};
trie* r = new trie;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] ^= s[i - 1];
        pos = i;
        r->insert(s[i],(1<<20));
    }
    int s1 = 0, s2 = 0;
    trie* c = r;
    for(int i=20;i>=0;i--)
    {
        if (r->next[1] != nullptr && c->next[0] != nullptr)
        {
            s1 += (1 << i);
            r = r->next[1];
            c = c->next[0];
        }
        else if (r->next[0] != nullptr && c->next[1] != nullptr)
        {
            s2 += (1 << i);
            r = r->next[0];
            c = c->next[1];
        }
        else if (r->next[0] != nullptr && c->next[0] != nullptr)
        {
            //s1 += (1 << i);
            r = r->next[0];
            c = c->next[0];
        } 
        else if (r->next[1] != nullptr && c->next[1] != nullptr)
        {
            s1 += (1 << i);
            s2 += (1 << i);
            r = r->next[1];
            c = c->next[1];
        }
    }
    sort(c->cnt.begin(), c->cnt.end());
    sort(r->cnt.begin(), r->cnt.end());

    cout << (s2 ^ s1) << ' ';
    if (s1 < s2)
        cout << c->cnt[0] + 1 << ' ' << r->cnt[0];
    else
        cout << r->cnt[0] + 1 << ' ' << c->cnt[0];
    return 0;
}