Cod sursa(job #2985239)

Utilizator LXGALXGA a LXGA Data 25 februarie 2023 23:25:15
Problema Xor Max Scor 10
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 = 1, y = 1;
    r->insert(0, 21);
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i - 1];
        s[i] ^= s[i - 1];
        int a = r->query(s[i], 21);
        if (ans < (s[i]^s[a]))
        {
            ans = s[i] ^ s[a];
            x = a + 1;
            y = i;
        }
        pos = i;
        r->insert(s[i],21);
    }
    cout << ans << ' ' << x << ' ' << y;
    
    return 0;
}