Cod sursa(job #3154269)

Utilizator Luka77Anastase Luca George Luka77 Data 3 octombrie 2023 22:41:17
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>
#define SIGMA 3
using namespace std;

/// INPUT / OUTPUT
const string problem = "xormax"; 
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");

/// DATA STRUCTURES
struct ans_type
{
    int st, maxi;
};

struct Trie
{
    struct Node
    {
        int rasp, poz;
        Node *sons[SIGMA];
    };

    Node *root = new Node();

    /// ADD A NUMBER IN ITS BINARY REPRESENTATION BY MOST SIGNIFICANT BIT
    inline void add(int x, int cnt, int position, Node *curr)
    {
        if(cnt == -1)
        {
            if(!curr->rasp)
            {
                curr->poz = position;
            }
            curr->rasp++;
            return;
        }
        int last_bit = ((x >> cnt) & 1);

        if(curr->sons[last_bit] == NULL)
            curr->sons[last_bit] = new Node();

        add(x, cnt - 1, position, curr->sons[last_bit]);
    }

    /// GETTING THE MAXIMUM XOR PER INTERVAL
    inline ans_type query(int x, int cnt, int ans, Node *curr)
    {
        if(cnt == -1)
        {
            return {curr->poz, ans};
        }

        int last_bit = ((x >> cnt) & 1);
        
        if(curr->sons[!last_bit])
        {
            ans += (1 << cnt);
            return query(x, cnt - 1, ans, curr->sons[!last_bit]);
        }
        else
            return query(x, cnt - 1, ans, curr->sons[last_bit]);
    }
};

/// GLOBAL VARIABLES
const int NMAX = 1e5 + 5;
int n, ans = 0, st = 0 , dr = 1;
int arr[NMAX], xors[NMAX];
Trie xor_max;

int main()
{
    /// IMPROVED INPUT / OUTPUT
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;

    for(int i = 1; i <= n; ++ i)
    {
        fin >> arr[i];
    }

    xor_max.add(0, 22, 0, xor_max.root);
    xors[1] = arr[1];
    xor_max.add(xors[1], 22, 1, xor_max.root);

    for(int i = 2; i <= n; ++ i)
    {
        xors[i] = xors[i - 1] ^ arr[i]; 
        xor_max.add(xors[i], 22, i, xor_max.root); 
        ans_type pos_ans = xor_max.query(xors[i], 22, 0, xor_max.root);
        if(pos_ans.maxi > ans)
        {
            ans = pos_ans.maxi;
            st = pos_ans.st;
            dr = i;
        }
    }
    fout << ans << ' ' << st + 1 << ' ' << dr << '\n';

    return 0;
}