Cod sursa(job #1462890)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 19 iulie 2015 13:18:46
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#define NMAX 100007
FILE *fin, *fout;
using namespace std;
int n, v[NMAX], temp, temp1, maxn, p1, p2;
struct trieNode
{
    int el;
    trieNode *child[2];
} root;
void trieInsert(trieNode *node, int pow)
{
    if(pow < 0)
    {
        node->el = temp;
        return;
    }
    int id = (v[temp] & (1<<pow))>>pow;
    if(node->child[id] == 0)
    {
        node->child[id] = new trieNode();
    }
    trieInsert(node->child[id], pow-1);
    return ;
}
int trieQuery(trieNode *node, int pow)
{
    if(pow < 0)
    {
        return node->el;
    }
    int id = not ((v[temp] & (1<<pow))>>pow);
    if(node->child[id])
    {
        return trieQuery(node->child[id], pow-1);
    }
    else return trieQuery(node->child[not id], pow-1);
}
int main()
{
    fin = freopen("xormax.in", "r", stdin);
    fout = freopen("xormax.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i<= n; ++i) scanf("%d", &v[i]);
    temp = 1;
    maxn = v[1];
    p1 = 1;
    p2 = 1;
    trieInsert(&root, 22);
    for(int i = 2; i<= n; ++i)
    {
        v[i] = v[i] xor v[i-1];
        temp = i;
        trieInsert(&root, 22);
        temp1 = trieQuery(&root, 22);
        temp = v[temp1] xor v[i];
        if(temp > maxn)
        {
            maxn = temp;
            p1 = temp1+1;
            p2 = i;
        }
        if(v[i] > maxn)
        {
            maxn = v[i];
            p1 = 1;
            p2 = i;
        }
    }
    printf("%d %d %d", maxn, p1, p2);
    fclose(fin);
    fclose(fout);
    return 0;
}