#include #define MAX_N 100000 #define MAX_BIT 63 #define NONE -1ll long long v[MAX_N]; /** * Partiționează elementele din intervalul [lo...hi] conform cu bitul bit. * Elementele cu 0 pe acea poziție merg în stânga, cele cu 1 în dreapta. * Returnează indicele primului element cu 1 (hi + 1 dacă nu există). **/ int partition(int lo, int hi, int bit) { // lo ... i - 1 = zerouri // i = elementul curent // i + 1 ... j = elemente neevaluate încă // j + 1 ... hi = unuuri int i = lo, j = hi; while (i <= j) { if ((v[i] >> bit) & 1) { long long tmp = v[i]; v[i] = v[j]; v[j] = tmp; j--; } else { i++; } } return i; } /** * Returnează xor-ul maxim între un element din intervalul [lo0...hi0] * și un element din intervalul [lo1...hi1], considerând doar biții de la * bit la 0. **/ long long max(int lo0, int hi0, int lo1, int hi1, int bit) { if (bit < 0) { return v[lo0] ^ v[lo1]; } int mid0 = partition(lo0, hi0, bit); int mid1 = partition(lo1, hi1, bit); // Căutăm un Xor între zerouri din stânga și unuuri din dreapta sau invers. // Dacă nu se poate, înseamnă că toți biții sunt egali în cele două mulțimi, // deci continuăm cu bitul următor. long long result1 = (mid0 > lo0 && mid1 <= hi1) ? max(lo0, mid0 - 1, mid1, hi1, bit - 1) : NONE; long long result2 = (mid0 <= hi0 && mid1 > lo1) ? max(mid0, hi0, lo1, mid1 - 1, bit - 1) : NONE; if (result1 != NONE || result2 != NONE) { return (result1 > result2) ? result1 : result2; } else { return max(lo0, hi0, lo1, hi1, bit - 1); } } int main(void) { int n; FILE *f = fopen("maxxor.in", "r"); fscanf(f, "%d", &n); for (int i = 0; i < n; i++) { fscanf(f, "%lld", &v[i]); } fclose(f); // Partiționăm după fiecare bit până când mulțimea se sparge în două int bit = MAX_BIT, mid; long long answer; do { bit--; mid = partition(0, n - 1, bit); } while (bit && ((v[0] >> bit) & 1) == ((v[n - 1] >> bit) & 1)); if (!bit) { answer = v[0] ^ v[n - 1]; // Numerele diferă cel mult pe ultimul bit } else { answer = max(0, mid - 1, mid, n - 1, bit - 1); } f = fopen("maxxor.out", "w"); fprintf(f, "%lld\n", answer); fclose(f); }