Cod sursa(job #2444446)

Utilizator StanCatalinStanCatalin StanCatalin Data 31 iulie 2019 16:02:27
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

const int dim = 100005;

int n,xo[dim];
long long int rasp = ((1LL<<21) + 1)*(-1);
vector <int> binar;

struct nod
{
    nod *c[2];
    int poz;
    nod()
    {
        c[0] = c[1] = NULL;
        poz = -1;
    }
};

void adauga(nod *root,int val)
{
    if (root == NULL)
    {
        root = new nod;
    }
    binar.clear();
    do
    {
        binar.push_back(val%2);
        val /= 2;
    }while (val != 0);
    while (binar.size() <= 20)
    {
        binar.push_back(0);
    }
    for (int i=binar.size()-1; i>=0; i--)
    {
        if (root->c[binar[i]] == NULL)
        {
            root->c[binar[i]] = new nod;
        }
        root = root->c[binar[i]];
        root->poz = i;
    }
}

long long int  raspuns(nod *root, int val)
{
    long long int now = 0;
    binar.clear();
    do
    {
        binar.push_back(val%2);
        val /= 2;
    }
    while (val != 0);
    while (binar.size() <= 20)
    {
        binar.push_back(0);
    }
    for (int i=binar.size()-1; i>=0; i--)
    {
        if (root->c[!binar[i]] != NULL)
        {
            now += (1LL<<(root->c[!binar[i]])->poz);
            root = root->c[!binar[i]];
        }
        else
        {
          /*  if (binar[i] == 1)
            {
                now += (1LL<<i);
            }*/
            root = root->c[binar[i]];
        }
    }
    return now;
}

int main()
{
    int val;
    in >> n;
    in >> xo[1];
    nod *start = new nod;
    long long int acm,val1;
    int st,dr;
    for (int i=2; i<=n; i++)
    {
        in >> val;
        xo[i] = xo[i-1]^val;
    }
    for (int i=2; i<=n; i++)
    {
        adauga(start,xo[i-1]);
        acm = raspuns(start , xo[i]);
        if (rasp < acm)
        {
            val1 = acm^xo[i];
            rasp = acm;
            dr = i;
        }
    }
    for (int i=dr-1; i>=1; i--)
    {
        if (xo[i] == val1)
        {
            st = i;
            break;
        }
    }
    out << rasp << " " << st+1 << " " << dr;
    return 0;
}