Pagini recente » Cod sursa (job #2537099) | Cod sursa (job #922605) | Cod sursa (job #2335885) | Cod sursa (job #1186439) | Cod sursa (job #2909619)
#include <stdio.h>
#include <utility>
#pragma GCC optimize("Ofast")
using namespace std;
FILE *fin, *fout;
const int SIGMA = 2;
const int DEPTH = 20;
const int INF = 1e9;
const int VMAX = (1 << 21) - 1;
int N;
int xuma, xuma0;
int maxi, start, stop;
struct Node {
int pos;
Node* children[SIGMA];
// Node () {
// pos = 0;
// for(int i = 0; i < SIGMA; i++) {
// children[i] = nullptr;
// }
// }
};
Node root;
void Insert(Node *root, const int &value, const int &pos, int index) {
if(index >= 0) {
bool x = (value & (1 << index)) != 0;
if(root->children[x] == nullptr) {
root->children[x] = new Node;
}
Insert(root->children[x], value, pos, index - 1);
} else {
root->pos = pos;
}
}
void Insert(const int &value, const int &pos) {
Insert(&root, value, pos, DEPTH);
}
pair<int, int> Prefix(Node *root, const int &value, const int &index, int answer = 0) {
if(index >= 0) {
bool x = (value & (1 << index)) != 0;
if(root->children[x] == nullptr) {
x ^= 1;
}
return Prefix(root->children[x], value, index - 1, answer + x * (1 << index));
} else {
return {answer, root->pos};
}
}
pair<int, int> Prefix(const int &value) {
return Prefix(&root, value, DEPTH);
}
int main () {
maxi = -INF;
Insert(0, 0);
fin = fopen("xormax.in", "r");
fscanf(fin, "%d", &N);
for(int i = 1; i <= N; i++) {
int x;
fscanf(fin, "%d", &x);
xuma ^= x; // hahaha ce amuzat, te-ai prins?
pair<int, int> p = Prefix(xuma ^ VMAX);
xuma0 = p.first;
if((xuma ^ xuma0) > maxi) {
maxi = (xuma ^ xuma0);
stop = i;
start = p.second + 1;
}
Insert(xuma, i);
}
fclose(fin);
fout = fopen("xormax.out", "w");
fprintf(fout, "%d %d %d\n", maxi, start, stop);
fclose(fout);
return 0;
}