Cod sursa(job #2068612)

Utilizator Coroian_DavidCoroian David Coroian_David Data 18 noiembrie 2017 09:51:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

#define MAX_N 100000
#define MAX_B 21

#define MAX_NR (1<<21)-1

using namespace std;

FILE *f, *g;

int n;
int rez = -1, stx, drx;

int last[MAX_NR + 1];

struct trie
{
    int ap[2];
};

trie a[MAX_N * MAX_B + 1];

int loc;

void alc(int &fiu)
{
    if(fiu != 0)
        return;

    fiu = (++ loc);
}

int ales;

int getRez(int poz, int bit, int x)
{
    if(bit < 0)
        return 0;

    int are = (x & (1 << bit)) != 0;

    if(a[poz].ap[1 - are] != 0)
    {
        ales |= (1 << bit) * (1 - are);
        return (1 << bit) + getRez(a[poz].ap[1 - are], bit - 1, x & ((1 << bit) - 1));
    }

    if(a[poz].ap[are] != 0)
    {
        ales |= (1 << bit) * are;
        return getRez(a[poz].ap[are], bit - 1, x & ((1 << bit) - 1));
    }

    return 0;
}

void baga(int poz, int bit, int x)
{
    if(bit < 0)
        return;

    int are = (x & (1 << bit)) != 0;

    if(a[poz].ap[are] == 0)
        alc(a[poz].ap[are]);

    baga(a[poz].ap[are], bit - 1, x & ((1 << bit) - 1));
}

void cmpRez(int nr, int st, int dr)
{
    if(nr > rez)
    {
        rez = nr;
        stx = st;
        drx = dr;
    }
}

void readFile()
{
    f = fopen("xormax.in", "r");

    fscanf(f, "%d", &n);

    baga(0, 20, 0);

    int i, nr;
    int x = 0;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &nr);

        x = x ^ nr;

        ales = 0;
        int cr = getRez(0, 20, x);

        cmpRez(nr, i, i);
        cmpRez(cr, last[ales] + 1, i);
        cmpRez(x, 1, i);

        baga(0, 20, x);

        last[x] = i;
    }

    fclose(f);
}

void printFile()
{
    g = fopen("xormax.out", "w");

    fprintf(g, "%d %d %d\n", rez, stx, drx);

    fclose(g);
}

int main()
{
    readFile();

    printFile();

    return 0;
}