Submission #1147131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147131		yasser	XOR (IZhO12_xor)	C++20	100 / 100	290 ms	53224 KiB

xor

#include <bits/stdc++.h>
using namespace std;
void Yasser() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

struct Node {
    int childs[2] {} ;
    int pre ;
    int &operator[](int x) {
        return childs[x] ;
    }
};
struct Trie {
    vector<Node> trie ;
    int newNode () {
        trie.emplace_back() ;
        return trie.size() - 1 ;
    }
    void clear () {
        trie.clear() ;
    }
    Trie () {
        clear() ;
        newNode() ;
    }
    bool sz (int node) {
        return (trie[node].pre > 0) ;
    }
    void insertOrremove (int x , int op) {
        int node = 0 ;
        for(int i = 30 ; i >= 0 ; i--) {
            int bit = x >> i & 1 ;
            if(trie[node][bit] == 0) {
                trie[node][bit] = newNode() ;
            }
            node = trie[node][bit] ;
            trie[node].pre += op ;
        }
    }

    int Query (int x) {
        int res = 0 ;
        int node = 0 ;
        for(int i = 30 ; i >= 0 ; i--) {
            int bit = x >> i & 1 ;
            if(trie[node][1 - bit]) {
                if(1 - bit) res |= (1 << i) ;
                node = trie[node][1 - bit] ;
            }else {
                if(bit) res |= (1 << i) ;
                node = trie[node][bit] ;
            }
        }
        return res ;
    }

};
void solve() {
    int n , x ; cin >> n >> x ;
    map<int , vector<int>>idxs ;
    idxs[0].emplace_back(0) ;
    vector<int> arr(n + 1) ;
    for(int i = 1 ; i<= n ; i++) {
        cin >> arr[i] ;
        arr[i] ^= arr[i - 1] ;
        idxs[arr[i]].emplace_back(i) ;
    }
    Trie triee ;
    triee.insertOrremove(0 , +1) ;
    int len = 0 ;
    int idx = 0 ;
    for(int i = 1 ; i<=n ; i++) {
        int z = triee.Query(arr[i]) ;
        if((z ^ arr[i]) >= x) {
            if(len < i - *idxs[z].begin()) {
                idx = *idxs[z].begin() + 1;
                len = i - *idxs[z].begin() ;
            }
        }
        triee.insertOrremove(arr[i] , +1) ;
    }

    cout << idx << ' ' << len << endl;
}

signed main() {
    ifstream cin("c.in");
    ofstream cout("c.out");
    int test_cases = 1;
    //cin >> test_cases;
    while(test_cases--) {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100