Cod sursa(job #1668741)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 30 martie 2016 00:30:03
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <stdio.h>
#include <string.h>
using namespace std;

int x[100001];
char* s;
int last = 0;

class trie
{
public:
    trie *v[2];
    int indice, nrfii;
    trie()
    {
        indice = nrfii = 0;
        v[0] = v[1] = NULL;
    }
    void ins(char *s, int pos)
    {
        if(*s == 2)
        {
            this -> indice = pos;
            return;
        }
        else
        {
            if(this -> v[*s] == NULL)
            {
                this -> v[*s] = new trie;
                this -> nrfii++;
            }
        }
        this -> v[*s] -> ins(s + 1, pos);
    }
    int pref(char *s)
    {
        if(*s == 2 || !this -> nrfii)
            return this -> indice;
        else
        {
            if(*s == 0)
            {
                if(this -> v[1])
                    return this -> v[1] -> pref(s + 1);
                else
                    return this -> v[0] -> pref(s + 1);
            }
            else
            {
                if(this -> v[0])
                    return this -> v[0] -> pref(s + 1);
                else
                    return this -> v[1] -> pref(s + 1);
            }
        }
    }
};

trie *nod = new trie;

char ans[22];

char* converter (int x) {
    for (int i = 0; i <= 20; i++) {
        ans[i] = 0;
    }
    ans[21] = 2;

    for (int pos = 20; x; x >>= 1, pos--) {
        ans[pos] = x & 1;
    }

    char* p;
    p = ans;
    return ans;
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("xormax.in", "r");
    fout = fopen("xormax.out", "w");


    int n;
    fscanf(fin, "%d", &n);

    for(int i = 1; i <= n; i++)
    {
        fscanf(fin, "%d", &x[i]);
        x[i] = (x[i] ^ x[i - 1]);
    }

    int max = 0, st, dr;

    for(int i = 1; i <= n; i++)
    {
        s = converter(x[i]);
        int val = nod -> pref(s);
        if((x[i] ^ x[val]) > max)
        {
            max = (x[i] ^ x[val]);
            st = val + 1;
            dr = i;
        }

        nod -> ins(s, i);
    }

    fprintf(fout, "%d %d %d", max, st, dr);

    return 0;
}