Cod sursa(job #2661435)

Utilizator FrostfireMagirescu Tudor Frostfire Data 21 octombrie 2020 23:36:58
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <fstream>

using namespace std;

ofstream g("xormax.out");

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
int n, nr;

struct date
{   int ans, pi, pf;
}sol, val;

struct Trie
{   int nrfii, cnt;
    Trie *fiu[3];
    Trie()
        {   fiu[0] = fiu[1] = 0;
            nrfii = cnt = 0;
        }
};

Trie *T = new Trie;

void ins(Trie *nod, int x, int bit, int idx)
{   if(bit < 0)
        {   nod->cnt = idx;
            return;
        }
    nr = 0;
    if(x & (1 << bit)) nr = 1;
    if(!nod->fiu[nr])
        {   nod->fiu[nr] = new Trie;
            nod->nrfii++;
        }
    ins(nod->fiu[nr], x, bit-1, idx);
}

date query(Trie *nod, int x, int bit, int idx, int curr)
{   if(bit < 0)
        {   date sol;
            sol.ans = curr;
            sol.pi = nod->cnt + 1;
            sol.pf = idx;
            return sol;
        }
    nr = 0;
    if(x & (1 << bit)) nr = 1;
    if(nod->fiu[1-nr])
        {   curr = (curr << 1) + 1;
            return query(nod->fiu[1-nr], x, bit-1, idx, curr);
        }
    else
        {   curr = (curr << 1);
            return query(nod->fiu[nr], x, bit-1, idx, curr);
        }
}

int main()
{
    InParser f("xormax.in");
    f >> n;
    int xr = 0;
    sol.ans = -1;
    ins(T, 0, 20, 0);
    for(int i=1; i<=n; i++)
        {   int x;
            f >> x;
            xr = xr ^ x;
            ins(T, xr, 20, i);
            val = query(T, xr, 20, i, 0);
            if(val.ans > sol.ans) sol = val;
        }
    if(sol.pi > sol.pf) sol.pi = sol.pf;
    g << sol.ans << ' ' << sol.pi << ' ' << sol.pf << '\n';
    return 0;
}