Cod sursa(job #2570917)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 4 martie 2020 19:59:18
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#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;
	}
};
//----------------------------------------
///Globale
int n,st,dr,rasp,d[1000001];
struct trie
{
    trie *z,*u;
    int who;
    trie()
    {
        z = NULL;
        u = NULL;
    }
}*r;
//----------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//----------------------------------------
int main()
{
    citire();
    rezolvare();
    afisare();
}
//----------------------------------------
void afisare()
{
    g << rasp << " " << st << " " << dr;
}
//----------------------------------------
int cauta(int val,int bit,trie *nod)
{
    if(bit == -1)
        return nod -> who;
    int x = val & (1 << bit);
    if(x == 0)
    {
        if(nod -> u != NULL)
            return cauta(val,bit - 1,nod -> u);
        else
            return cauta(val,bit - 1,nod -> z);
    }
    else
    {
        if (nod -> z != NULL)
            return cauta(val,bit - 1,nod -> z);
        else
            return cauta (val,bit - 1,nod -> u);
    }
}
//----------------------------------------
trie* adauga(int i,int bit,trie*nod)
{
    if(nod == NULL)
        nod = new trie;
    if(bit == -1)
    {
        nod -> who = i;
        return nod;
    }
    int x = d[i] & (1 << bit);
    if(x == 0)
        nod -> z = adauga(i,bit - 1,nod -> z);
    else
        nod -> u = adauga(i,bit - 1,nod -> u);
    return nod;
}
//----------------------------------------
void rezolvare()
{
    rasp = -1;
    r = adauga(0,21,r);
    for(int i = 1; i <= n; ++i)
    {
        int gasit = cauta(d[i],21,r);
        if((d[gasit] ^ d[i]) > rasp)
        {
            rasp = d[gasit] ^ d[i];
            dr = i;
            st = gasit + 1;
        }
        r = adauga(i,21,r);
    }
}
void citire()
{
    InParser f("xormax.in");
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        int x;
        f >> x;
        d[i] = d[i - 1] ^ x;
    }
}