Cod sursa(job #3309833)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 9 septembrie 2025 15:46:46
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <bits/stdc++.h>
#define int long long
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int Nmax = 1e5 + 1;
const int L = 21;
int n, x, v[Nmax];
struct Node
{
    int fin = -1;
    Node* sons[2];
    Node() { sons[0] = sons[1] = nullptr; }
};

Node* trie = nullptr;

Node* add(Node* p, const char* w, int idx)
{
    if(p == nullptr)
        p = new Node;
    if(w[0] == '\0')
        p->fin = idx;
    else
        p->sons[w[0] - '0'] = add(p->sons[w[0] - '0'], w + 1, idx);
    return p;
}

string t_string(int x)
{
    string s(L, '0');
    for (int i = L - 1; i >= 0; i--)
    {
        s[i] = (x & 1) ? '1' : '0';
        x >>= 1;
    }
    return s;
}
string val;
int query(Node* p, int pos)
{
    if(p == nullptr)
        return -1;
    if(pos < (int)val.size())
    {
        Node* bit1 = p->sons[1];
        Node* bit0 = p->sons[0];
        if(val[pos] == '0')
        {
            if(bit1 != nullptr)
                return query(bit1, pos + 1);
            else
                return query(bit0, pos + 1);
        }
        else
        {
            if(bit0 != nullptr)
                return query(bit0, pos + 1);
            else
                return query(bit1, pos + 1);
        }
    }
    else
        return p->fin;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> n;
    v[0] = 0;
    int maxi = 0;
    int start = 0, finish = 0;

    for(int i = 0; i < L; i++)
        s.push_back('0');
    trie = add(trie , s.c_str(), 0);

    for(int i=1; i<=n; i++)
    {
        cin >> x;
        v[i] = v[i - 1] ^ x;
        val = t_string(v[i]);
        int j = query(trie, 0);
        if(j != -1 && (v[i] ^ v[j]) > maxi)
        {
            maxi = v[i] ^ v[j];
            finish = i;
            start = j + 1;
        }
        trie = add(trie, val.c_str(), i);
    }
    cout << maxi << " " << start << " " << finish;
    return 0;
}