Cod sursa(job #3041339)

Utilizator Tudor06MusatTudor Tudor06 Data 31 martie 2023 12:22:03
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;

const int MAXBITS = 21;
const int VALMAX = ( 1 << MAXBITS );
const int NMAX = 1e5;

long long freq[VALMAX + 1];

void FWHT( int st = 0, int dr = VALMAX ) {
    if ( dr - st == 1 ) return;
    int mij = st + ( dr - st ) / 2;
    FWHT( st, mij );
    FWHT( mij, dr );
    for ( int i = 0; i < mij - st; i ++ ) {
        long long a = freq[st + i], b = freq[mij + i];
        freq[st + i] = a + b;
        freq[mij + i] = a - b;
    }
}

int v[NMAX + 1];
int main() {
    ifstream fin( "xormax.in" );
    ofstream fout( "xormax.out" );
    int n;
    fin >> n;
    for ( int i = 1; i <= n; i ++ ) {
        fin >> v[i];
        v[i] ^= v[i - 1];
        freq[v[i]] ++;
    }
    int ans = 0;
    FWHT();
    for ( int i = 0; i < VALMAX; i ++ ) freq[i] *= freq[i];
    FWHT();
    for ( int i = 0; i < VALMAX; i ++ ) {
        if ( freq[i] / VALMAX / 2 > 0 ) ans = i;
        freq[i] = -1;
    }
    freq[0] = 0;
    for ( int i = 1; i <= n; i ++ ) {
        if ( freq[v[i] ^ ans] != -1 ) {
            fout << ans << ' ' << freq[v[i] ^ ans] + 1 << ' ' << i;
            break;
        }
        freq[v[i]] = i;
    }
	return 0;
}