Cod sursa(job #3309818)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 9 septembrie 2025 11:14:41
Problema Xor Max Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>
#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 = 31;
int n, x, v[Nmax];
struct Node
{
    int fin = -1;
    vector<Node*> sons;
    Node(): sons(2, 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;
    if(x == 0) s.push_back('0');
    while(x)
    {
        if(x & 1)
            s.push_back('1');
        else
            s.push_back('0');
        x >>= 1;
    }
    while((int)s.size() < L)
        s.push_back('0');
    reverse(s.begin(), s.end());
    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;
}

int 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;
}