Cod sursa(job #3309759)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 8 septembrie 2025 15:30:21
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 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 = -1;
    vector<Node*> sons;
    Node(): sons(2, nullptr) {}
    ~Node() {
        for (auto child : sons)
            if (child) delete child;
    }
};

Node* add(Node* p, const char* w, int idx)
{
    if (p == nullptr) p = new Node;
    if (w[0] == '\0')
        p->fin = idx;
     else
    {
        int bit = w[0] - '0';
        p->sons[bit] = add(p->sons[bit], 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)
                return query(bit1, pos + 1);
            else
                return query(bit0, pos + 1);
        }
        else
        {
            if (bit0)
                return query(bit0, pos + 1);
            else
                return query(bit1, pos + 1);
        }
    }
    return p ? p->fin : 0;
}

static inline string make_key_from_number(int val)
{
    string p;
    for (int j = 0; j < L; j++)
        p.push_back((val & (1 << (L - 1 - j))) ? '1' : '0');
    return p;
}
int main()
{
    cin >> n;
    v[0] = 0;

    int maxi = -1;
    int start = 0, stop = 0;

    Node* trie = nullptr;


    s = make_key_from_number(0);
    trie = add(trie, s.c_str(), 0);

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

        s = make_key_from_number(v[i]);

        int j = query(trie, 0);

        if ((v[i] ^ v[j]) > maxi)
        {
            maxi = v[i] ^ v[j];
            start = j;
            stop = i;
        }

        trie = add(trie, s.c_str(), i);
    }

    cout << maxi << " " << start + 1 << " " << stop;
    return 0;
}