Cod sursa(job #3135098)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 1 iunie 2023 20:20:45
Problema Xor Max Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

int sor[100001];
map <int, int> mp[21];

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        sor[i] = sor[i - 1] ^ x;
    }
    for(int i = 0; i < 21; i++)
        mp[i][0] = 0;
    assert(mp[0].find(0) != mp[0].end());
    int max1 = -1, st, dr;
    for(int i = 1; i <= n; i++)
    {
        int pref = 0;
        for(int pas = 20; pas >= 0; pas--)
        {
            if(!((1 << pas) & sor[i]))
                pref += (1 << pas);
            if(mp[pas].find(pref) != mp[pas].end())
                continue;
            if(!((1 << pas) & sor[i]))
                pref -= (1 << pas);
            else
                pref += (1 << pas);
        }
        if((sor[i] ^ pref) > max1)
        {
            max1 = (sor[i] ^ pref);
            dr = i;
            st = mp[0][pref] + 1;
        }
        pref = 0;
        for(int pas = 20; pas >= 0; pas--)
        {
            pref += ((1 << pas) & sor[i]);
            mp[pas][pref] = i;
        }
    }
    cout << max1 << " " << st << " " << dr;
    return 0;
}