Cod sursa(job #3123585)

Utilizator matwudemagogul matwu Data 24 aprilie 2023 20:14:25
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <bits/stdc++.h>
using namespace std;
#define ezurect int T; cin >> T; while(T--){solve();}
const int N = 1e5 + 1;
int n;
vector<int> v(N);
vector<long long> sp(N);
long long ans, st = 1e9, dr, mda = 1e9;
struct Trie{
    int cnt;
    int minim = 1e9;
    Trie* next[2] = {};
    void insert(long long nr, int pos, int i){
        if(pos == -1){
            minim = min(minim, i);
        }else{
            if(nr & (1 << pos)){
                if(!next[1]){
                    next[1] = new Trie;
                }
                next[1]->insert(nr, pos - 1, i);
            }else{
                if(!next[0]){
                    next[0] = new Trie;
                }
                next[0]->insert(nr, pos - 1, i);
            }
        }
    }

    int take_maxim(long long nr, int pos, long long& res){
        if(pos == -1){
            return minim;
        }else{
            if(nr & (1 << pos)){
                if(next[0]){
                    res += (1 << pos);
                    return next[0]->take_maxim(nr, pos - 1, res);
                }else if(next[1]){
                    return next[1]->take_maxim(nr, pos - 1, res);
                }else{
                    return minim;
                }
            }else{
                if(next[1]){
                    res += (1 << pos);
                    return next[1]->take_maxim(nr, pos - 1, res);
                }else if(next[0]){
                    return next[0]->take_maxim(nr, pos - 1, res);
                }else{
                    return minim;
                }
            }
        }
    }
};

int log(long long a){
    if(!a) return 0;
    return log2(a);
}
int main(){
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    fin.tie(0)->sync_with_stdio(0);
    fin >> n;

    Trie trie;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
        sp[i] = sp[i - 1] ^ v[i];
        if(ans < v[i]){
            ans = v[i];
            st = i, dr = i;
        }
    }


    trie.insert(sp[1], 21, 1);
    for(int i = 2; i <= n; i++){
        long long port = 0;
        int maxim = trie.take_maxim(sp[i], 21, port);
        if(maxim != 1e9){
         //   cout << port << " " << maxim << " " << i << '\n';
            if(ans < port){
                ans = port;
                st = maxim;
                dr = i;
                mda = dr - st + 1;
            }
            else if(ans == port){
                if(st > maxim){
                    st = maxim;
                    dr = i;
                    mda = dr - st + 1;
                }
                else if(st == maxim){
                    if(dr - st + 1 < mda){
                        mda = dr - st + 1;
                        dr = i;
                    }
                }
            }
        }
        trie.insert(sp[i], 21, i);
    }

    fout << ans << " " << st + 1 << " " << dr;

}