Submission #1102426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102426		AlexRex0	XOR (IZhO12_xor)	C++14	100 / 100	324 ms	60748 KiB

xor

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 250005 * 30;

pair<int, int> trie[maxn][4];
int node_count = 0;
bool stop[maxn];

void insert(string word, int pi){
    int node = 0;
    for(char c: word){
        if(trie[node][c - '0'].first == 0){
            trie[node][c - '0'] = {++node_count, pi};
        }
        node = trie[node][c - '0'].first;
    }
    stop[node] = true;
}

int n, x;
int posAns = 0, ans = 0;

void buscar(string s, int i){
    pair<int, int> node = {0, 0};
    for(int j = 0; j < s.size(); ++j){
        /// no la encontro
        if(trie[node.first][s[j] - '0'].first == 0){
            node.first = 0;
            break;
        }
        node = trie[node.first][s[j] - '0'];
    }
    if(node.first){
        /// si la encontro
        int tam = i - node.second;
        if(tam > ans){
            ans = tam;
            posAns = node.second + 1;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;

    /// inserto la cadena vacia
    string ini = "";
    for(int i = 0; i <= 29; ++i) ini+= "0";
    insert(ini, 0);
    ///
    int acum = 0;
    for(int i = 1; i <= n; ++i){
        int v; cin >> v;
        acum^= v;

        /// s es la cadena que voy a buscar
        string s = "";
        for(int k = 29; k >= 0; --k){
            /// busco uno apagado
            if( !(x & (1 << k)) && (acum & (1 << k)) ){
                s+="0";
                buscar(s, i);
                s.pop_back();
            }
            /// busco uno prendido
            if( !(x & (1 << k)) && !(acum & (1 << k)) ){
                s+="1";
                buscar(s, i);
                s.pop_back();
            }
            if( !(x & (1 << k)) && !(acum & (1 << k)) ){
                s+="0";
            }
            if( !(x & (1 << k)) && (acum & (1 << k)) ){
                s+="1";
            }
            if( (x & (1 << k)) && !(acum & (1 << k)) ){
                s+="1";
            }
            if( (x & (1 << k)) && (acum & (1 << k)) ){
                s+="0";
            }
        }
        /// busco la cadena exactamente igual a x
        //cout << s << "\n";
        buscar(s, i);

        string nueva = "";
        for(int j = 29; j >= 0; --j){
            if(acum & (1 << j)) nueva+= "1";
            else nueva+= "0";
        }
        insert(nueva, i);

    }
    cout << posAns << ' ' << ans << "\n";
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void buscar(std::string, int)':
xor.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int j = 0; j < s.size(); ++j){
      |                    ~~^~~~~~~~~~

• Subtask 1: 100 / 100