Cod sursa(job #3277117)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 15 februarie 2025 12:27:20
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1e5 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("xormax.in");
    ofstream out("xormax.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N;
int rasp =-1, st, dr;
int v[NMAX], pref[NMAX];

struct Trie
{
    int stop;
    Trie *fii[2];
};

Trie* root = new Trie();
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N;
    for (int i = 1 ; i <= N ; ++ i) cin >> v[i];
}
///-------------------------------------
Trie* adauga(Trie* root, int idx, int nr, int bit)
{
    if (root == nullptr) root = new Trie();

    if (bit == -1)
    {
        root->stop = idx;
        return root;
    }

    bool curr = (nr & (1 << bit)) > 0;
    root->fii[curr] = adauga(root->fii[curr], idx, nr, bit - 1);
    return root;
}
///-------------------------------------
int query(Trie *root, int nr, int bit)
{
    if (bit == -1) return root->stop;

    bool curr = (nr & (1 << bit)) > 0;
    if (root->fii[!curr] != nullptr)
        return query(root->fii[!curr], nr, bit - 1);
    
    return query(root->fii[curr], nr, bit - 1);
}
///-------------------------------------
inline void Solution()
{
    for (int i = 1 ; i <= N ; ++ i) pref[i] = (pref[i - 1] ^ v[i]);

    for (int i = 0 ; i <= N ; ++ i)
    {
        root = adauga(root, i, pref[i], 20);
        int idx_complement = query(root, pref[i], 20);
        int oth = pref[idx_complement];
        int xorr = (pref[i] ^ oth);

        if (rasp < xorr)
        {
            rasp = xorr;
            st = idx_complement + 1;
            dr = i;
        }
    }
}
///-------------------------------------
inline void Output()
{
    cout << rasp << " " << st << " " << dr;
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}