Cod sursa(job #2205390)

Utilizator mlc_oficialBoris Barca mlc_oficial Data 18 mai 2018 23:22:36
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5;

int a[kMaxN + 2], idx[kMaxN + 2];
int pred[kMaxN + 3], succ[kMaxN + 3];

void Delete(int pos) {
    pred[succ[pos]] = pred[pos];
    succ[pred[pos]] = succ[pos];
}

void Insert(int pos) {
    pred[succ[pos]] = succ[pred[pos]] = pos;
}

int main() {
#ifdef INFOARENA
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
#endif

    int n; cin >> n;
    for (int i = 2; i <= n + 1; ++i) {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    
    iota(idx + 1, idx + n + 2, 1);
    sort(idx + 1, idx + n + 2, [](const int u, const int v) { return a[u] > a[v]; });
    
    for (int i = 0; i <= n + 2; ++i) {
        pred[i] = i - 1;
        succ[i] = i + 1;
    }
    
    for (int i = n + 1; i > 0; --i) {
        Delete(idx[i]);
    }
    
    int best = 0, sol[2] = {1 << 30};
    for (int i = 1; i <= n + 1; ++i) {
        const int pivot = idx[i];
        Insert(pivot);
        for (int j = pred[pivot]; j; j = pred[j]) {
            if (a[pivot] + a[j] < best) {
                break;
            }
            
            const int xor_sum = a[pivot] ^ a[j];
            if (xor_sum > best) {
                best = xor_sum;
                sol[0] = j;
                sol[1] = idx[i];
            } else if (xor_sum == best 
                  and (j < sol[0] or (j == sol[0] and idx[i] < sol[1]))
            ) {
                sol[0] = j;
                sol[1] = idx[i];
            }
        }
    }
    cout << best << ' ' << sol[0] << ' ' << sol[1] - 1 << endl;
}