Cod sursa(job #2890072)

Utilizator dnprxDan Pracsiu dnprx Data 14 aprilie 2022 12:00:19
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<bits/stdc++.h>
using namespace std;

struct Trie
{
    int poz;
    Trie *leg[2];
    Trie(int p)
    {
        poz = p;
        leg[0] = leg[1] = NULL;
    }
};
Trie *rad;
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;
	}
};
InParser fin("xormax.in");
ofstream fout("xormax.out");

void Adauga(int w, int ind)
{
    int i, j;
    Trie *q, *p = rad;
    for (i = 20; i >= 0; i--)
    {
        j = (w >> i) & 1;
        if (p->leg[j] != NULL) p = p->leg[j];
        else
        {
            q = new Trie(0);
            p->leg[j] = q;
            p = q;
        }
    }
    if (p->poz == 0) p->poz = ind;
}

void ValMax(int w, int &M, int &P)
{
    int i, j;
    Trie *p = rad;
    M = 0;
    for (i = 20; i >= 0; i--)
    {
        j = (w >> i) & 1;

        if (p->leg[1-j] != NULL)
        {
            M = M | (1 << i);
            p = p->leg[1 - j];
        }
        else if (p->leg[j] != NULL) p = p->leg[j];
        else {P = p->poz; return;}
    }
    P = p->poz;
}

int main()
{
    int n, i, w, x, answer = -1, st, dr, v, P;
    rad = new Trie(0);
    fin >> n;
    w = st = dr = 0;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        if (answer < x)
        {
            answer = x;
            st = dr = i;
        }
        w = w ^ x;
        if (i > 1)
        {
            ValMax(w, v, P);
            if (answer < v)
            {
                answer = v;
                st = P + 1; dr = i;
            }
        }
        Adauga(w, i);
    }
    fout << answer << " " << st << " " << dr << "\n";
    fout.close();
    return 0 ;
}