Cod sursa(job #2287867)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 22 noiembrie 2018 16:46:58
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#define ll long long

#define PII pair < int , int >

#define MOD 1000000007

using namespace std;

int n, m, data, xorr, mx, st = 1, en = 1;

struct trieNode {

int value, en;

struct trieNode *child[2];

trieNode() {

child[0] = child[1] = NULL;

value = 0;

}

};

trieNode* root;

trieNode* create() {

trieNode* newNode = new trieNode;

return newNode;

}

void add(int number, int pos) {

trieNode* curr = root;

for (int i = 31; i >= 0; i--) {

bool u = ((number >> i) & 1);

if (curr->child[u] == NULL)

curr->child[u] = create();

curr = curr->child[u];

}

curr->en = pos;

curr->value = number;

}

PII search(int number) {

trieNode* curr = root;

for (int i = 31; i >= 0; i--) {

bool u = ((number >> i) & 1);

if (curr->child[u ^ 1] != NULL) {

curr = curr->child[u ^ 1];

} else if (curr->child[u] != NULL) {

curr = curr->child[u];

}

}

return make_pair(number ^ (curr->value), curr->en);

}

int main(){

ios_base::sync_with_stdio(0);

cin.tie(NULL);

ifstream cin("xormax.in");

ofstream cout("xormax.out");

root = create();

cin >> n;

xorr = 0; add(xorr, 0);

for (int i = 1; i <= n; i++) {

cin >> data;

if (i == 1) mx = data;

xorr ^= data;

add(xorr, i);

PII res = search(xorr);

if (res.first > mx || (res.first == mx && i < en) || (res.first == mx && i == en && res.second + 1 > st && res.second + 1 <= en)) {

mx = res.first;

st = res.second + 1;

en = i;

} 

}

cout << mx << " " << st << " " << en;

return 0;

}