Submission #1149228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149228		hoksha	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

#include "bits/stdc++.h"
using namespace std;
const int M = 31;
struct Node{
   int ch[2]{};
   int sz = 0;
   int mnIndex = 1e9;
   int isEnd = 0;
   int &operator[](char x){
       return ch[x];
   }
};
struct Trie{
    vector<Node>trie;

    int newNode(){
        trie.emplace_back();
        return trie.size() - 1;
    }
    Trie(){init();}
    void init() {
        trie.clear();
        trie.emplace_back();
    }
    void update(int x, int in, int cur = 0, int i = M - 1) {
        if (i == -1) {
            trie[cur].isEnd++;
            trie[cur].sz++;
            trie[cur].mnIndex = min(trie[cur].mnIndex, in);
            return;
        }

        int bit = (x >> i) & 1;
        if (trie[cur][bit] == 0) trie[cur][bit] = newNode();

        update(x, in, trie[cur][bit], i - 1);
        trie[cur].sz++;
        trie[cur].mnIndex = min(trie[cur].mnIndex, trie[trie[cur][bit]].mnIndex);
    }

    int getAns(int pre, int x){
        int cur = 0;
        int minAns = 1e9;
        bool ok = true;
        for(int i = M; i >= 0; --i){
            int bitP = pre >> i & 1;
            int bitX = x >> i & 1;
            if (bitP == 1 && bitX == 0){
                if (trie[cur][0]){
                    minAns = min(minAns, trie[trie[cur][0]].mnIndex);
                }
            }
            else if (bitP == 0 && bitX == 0){
                if (trie[cur][1]){
                    minAns = min(minAns, trie[trie[cur][1]].mnIndex);
                }
            }


            if (trie[cur][bitP ^ bitX]){
                cur = trie[cur][bitP ^ bitX];
            }
            else {
                ok = false;
                break;
            }
        }
        if(trie[cur].isEnd){
            minAns = min(minAns, trie[cur].mnIndex);
        }
        return minAns;
    }


};
void fast() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(0);

}
int main(){
   fast();
   int n, x; cin >> n >> x;
   vector<int>a(n + 1);
   for(int i = 1; i <= n; ++i){
       cin >> a[i];
       a[i] ^= a[i - 1];
   }
   Trie trie;
   trie.update(0, 0);
   int L = 1, R = 0;
   for(int i = 1; i <= n; i++){
       int left = trie.getAns(a[i], x);
       if (left != 1e9) {
           if (i - left > R - L + 1) {
               L = left + 1;
               R = i;
           } else if (i - left == R - L + 1 && left + 1 < L) {
               L = left + 1;
               R = i;
           }
       }
       trie.update(a[i], i);
   }
   cout << L << ' ' << R - L + 1 << endl;





    return 0;
}

• Subtask 1: 0 / 100