Cod sursa(job #3309758)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 8 septembrie 2025 15:23:38
Problema Xor Max Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int L = 31;
const int Nmax = 1e5 + 1;
int n, st, dr, x, v[Nmax];
struct Node
{
    int fin = 0;
    vector<Node*> sons;
    Node():sons(2){}
    ~Node()
    {
        for(int i=0; i<2; i++)
            if(this->sons[i] != nullptr)
                delete this->sons[i];
    }
};
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;   // salvăm indexul prefixului inserat
    else
        p->sons[w[0] - '0'] = add(p->sons[w[0] - '0'], w + 1, idx);
    return p;
}

string s;

int query(Node* p, int pos)
{
    if(pos < (int)s.size() && p != nullptr)
    {
        Node* bit1 = p->sons[1];
        Node* bit0 = p->sons[0];
        if(s[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);
        }
    }
    return p ? p->fin : 0;
}

static inline string make_key_from_pattern(string p)
{
    reverse(p.begin(), p.end());
    if((int)p.size() < L)
        p.resize(L, '0');
    return p;
}

int main()
{
    int maxi = -1;
    cin >> n;
    v[0] = 0;

    // inserează prefixul inițial 0 cu index 0
    s.assign(L, '0');
    trie = add(trie, s.c_str(), 0);

    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        v[i] = v[i - 1] ^ x;

        // construiește cheia binară pentru prefixul v[i]
        s.clear();
        int y = v[i];
        if(y == 0) s.push_back('0');
        while(y)
        {
            if(y & 1) s.push_back('1');
            else      s.push_back('0');
            y >>= 1;
        }
        s = make_key_from_pattern(s);

        int start = query(trie, 0);

        if((v[i] ^ v[start]) > maxi)
        {
            maxi = v[i] ^ v[start];
            st = start;
            dr = i;
        }

        trie = add(trie, s.c_str(), i);  // inserează prefixul curent cu indexul lui
    }

    cout << maxi << " " << st + 1 << " " << dr;
    return 0;
}