Cod sursa(job #3255968)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 12 noiembrie 2024 20:34:14
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#include <algorithm>
#include <iterator>
#define in fin
#define out fout

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct node{
    node* v[2]; // pentru copilul care duce 0 si 1

    node(){
        for(int i = 0; i < 2; i++){
            v[i] = NULL;
        }
    }
};
node* r = new node();

void add(node* nod, string & s, int i){
    if(i == s.size()){
        return;
    }

    if( nod->v[ s[i] - '0' ] == NULL ){
        nod->v[ s[i] - '0' ] = new node();
    }

    add( nod->v[ s[i] - '0' ], s, i + 1 );
}

string sol;
void query(node* nod, string & s, int i){
    if(i == s.size()){
        return;
    }

    int wanted = 1 - (s[i] - '0');
    if(nod->v[ wanted ] == NULL) wanted = 1 - wanted;
    if(nod->v[ wanted ] == NULL) return;

    sol.push_back( char(wanted + '0') );

    query( nod->v[ wanted ], s, i + 1 );
}

string binar(int nr){
    string s;
    while(nr){
        s.push_back( char('0' + nr % 2) );
        nr /= 2;
    }
    while(s.size() < 22) s.push_back('0');
    reverse(s.begin(), s.end());
    return s;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n; in >> n;
    int v[n];

    for(int i = 0; i < n; i++) in >> v[i];
    int xr[n + 1];
    xr[0] = 0;
    string aa = binar(0);
    add(r, aa, 0);
    int maxi = INT_MIN;
    int v1 = -1, p = 0;
    for(int i = 1; i <= n; i++){
        xr[i] = (xr[i - 1] ^ v[i - 1]);
        sol.clear();
        aa = binar( xr[i] );
        query(r, aa, 0);
        int nr = 0;
        for(int i = sol.size() - 1; i >= 0; i--) nr = nr + (1 << (sol.size() - i - 1)) * (sol[i] - '0');

        if( (nr ^ xr[i]) > maxi ){
            maxi = (nr ^ xr[i]);
            p = i;
            v1 = nr;
        }
        // cout << "i = " << i << " maxi = " << maxi << '\n';
        add( r, aa, 0 );
    }
    int p2 = p - 1;
    while(p2 > 0 && xr[p2] != v1) p2--;
    out << maxi << " " << p2 + 1 << " " << p << '\n';

    return 0;
}