Cod sursa(job #2985234)

Utilizator LXGALXGA a LXGA Data 25 februarie 2023 23:13:57
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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
{
    int cnt;
    trie* next[2];
    trie()
    {
        cnt = 0;
        next[0] = nullptr;
        next[1] = nullptr;
    }
    void insert(int nr,int p)
    {
        if (p == 0)
            cnt = pos;
        else
        {
            int ok = nr >> p & 1;
            if (next[ok] == nullptr)
                next[ok] = new trie;
            next[ok]->insert(nr, p - 1);
        }
    }
    int query(int nr, int p)
    {
        if (p == 0)
            return cnt;
        else
        {
            int ok = nr >> p & 1;
            if (next[!ok] != nullptr)
                return next[!ok]->query(nr, p - 1);
            else
                return next[ok]->query(nr, p - 1);
        }
    }
};
trie* r = new trie;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    int ans = 0, x = 0, y = 0;
    r->insert(0, 20);
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] ^= s[i - 1];
        int a = r->query(s[i], 20);
        if (ans < (s[i]^s[a]))
        {
            ans = s[i] ^ s[a];
            x = a + 1;
            y = i;
        }
        pos = i;
        r->insert(s[i],20);
    }
    cout << ans << ' ' << x << ' ' << y;
    
    return 0;
}