Cod sursa(job #2031087)

Utilizator al_k_ponyClaudiu Babin al_k_pony Data 2 octombrie 2017 18:24:45
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

struct data
{
    int nxt[2];
}tpl;

int n,a[1 << 17],lst[1 << 21],idx,mx,x;
vector<data>vec;

void add(int x)
{
    int curr = 0;
    for(int i = 20;i + 1;i--)
    {
        int a = ((x & (1 << i)) > 0);
        if(!vec[curr].nxt[a]){
            vec[curr].nxt[a] = ++idx;
            vec.pb(tpl);
        }
        curr = vec[curr].nxt[a];
    }
}

int f(int x)
{
    int curr = 0;
    int ans = 0;
    for(int i = 20;i + 1;i--)
    {
        int a = ((x & (1 << i)) > 0);
        if(vec[curr].nxt[!a]) {
            ans += (1 << i);
            curr = vec[curr].nxt[!a];
        }
        else curr = vec[curr].nxt[a];
    }
    return ans;
}

int32_t main(){_
    //freopen("input","r",stdin);
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    cin >> n;
    tpl = {};vec.pb(tpl);add(x);
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        x ^= a[i];
        mx = max(mx,f(x));
        add(x);
    }
    lst[0] = 0;
    for(int i = 1;i < (1 << 21);i++) lst[i] = -1;
    x = 0;
    for(int i = 1;i <= n;i++)
    {
        x ^= a[i];
        if(lst[x ^ mx] != -1) rc(mx << ' ' << lst[x ^ mx] + 1 << ' ' << i);
        lst[x] = i;
    }
}