Cod sursa(job #2683726)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 12 decembrie 2020 00:48:01
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("xormax.in");
ofstream out("xormax.out");

int v[100005];

int i;
struct TrieNode {
    int nr;
    TrieNode *next[2];
    TrieNode() : nr(0) {
     	next[0]=0;
		next[1]=0;
    }
};

TrieNode *root;
void insert(TrieNode *currentNode, int b, int nr) {
   
    if(b==-1)
	{
		currentNode->nr=i;
		return;
	}
		bool x=nr&(1<<b);
		if(currentNode->next[x] == NULL)
			currentNode->next[x] = new TrieNode;
		insert(currentNode->next[x],b-1,nr);
}

int search(TrieNode *currentNode,int b,int nr)
{
	if(b==-1)
		return currentNode->nr;
	bool x=nr&(1<<b);
	if(currentNode->next[1-x] != NULL)
		return search(currentNode->next[1-x],b-1,nr);
	return search(currentNode->next[x],b-1,nr);
	
}
int main() 
{
	int n;
	in>>n;
	int maxx=0;
	root=new TrieNode;
	int ansi,ansj;
	insert(root,20,0);
	for(i=1;i<=n;i++)
	{
		int x;
		in>>x;
		v[i]=(x^v[i-1]);
		int j=search(root,20,v[i]);
		if((v[i]^v[j])>maxx)
		{
			ansi=i;
			ansj=j+1;
			maxx=(v[i]^v[j]);
		}
		else
		{
			if(v[i]^v[j]==maxx)
				if(i<ansi)
				{
					ansi=i;
					ansj=j+1;
				}
				else if(i==ansi && j+1>ansj)
					ansj=j+1;
		}
		insert(root,20,v[i]);

	}
	out<<maxx<<" "<<ansj<<" "<<ansi;
    return 0;
}