Cod sursa(job #2217386)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 30 iunie 2018 11:28:50
Problema Xor Max Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

#define NM 100002
#define VM 5000000

using namespace std;

int n, sp[NM];
int ap[VM];

bool f(int x, int &a, int &b)
{
    for(int i = 1; i <= n; i++)
        ap[sp[i]] = 0;
    for(int i = 1; i <= n; i++)
    {
        int x1 = x ^ sp[i];
        if(x1 == 0)
        {
            a = i;
            b = i;
            return 1;
        }
        if(ap[x1] != 0)
        {
            a = ap[x1] + 1;
            b = i;
            return 1;
        }
        ap[sp[i]] = i;
    }
    a = b = -1;
    return 0;
}

int main()
{
    ifstream fin ("xormax.in");
    ofstream fout ("xormax.out");
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        int e;
        fin >> e;
        sp[i] = sp[i - 1] ^ e;
    }
    int l = 0, r = 5000000, mid;
    while(l < r)
    {
        int aux1, aux2;
        mid = (l + r + 1) / 2;
        if(f(mid, aux1, aux2) == 0)
            r = mid - 1;
        else
            l = mid;
    }
    int start, stop;
    f(l, start, stop);
    fout << l << " " << start << " " << stop << "\n";
    return 0;
}