Submission #1010137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010137		vjudge1	XOR (IZhO12_xor)	C++17	100 / 100	105 ms	26284 KiB

xor

#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int inf = 3e5;

struct Trie{
    struct node{
        int nxt[2];
        int mn;
        node(){
            memset(nxt,-1,sizeof(nxt));
            mn = inf;
        }
    };
    vector<node> trie;
    Trie(){
        trie.emplace_back();
    }

    void insert(int x,int ind){
        int cur = 0;
        for(int i = 31; i >= 0; i--){
            int b = (x >> i) & 1;
            if(trie[cur].nxt[b] == -1){
                trie[cur].nxt[b] = trie.size();
                trie.push_back(node());
            }
            cur = trie[cur].nxt[b];
            trie[cur].mn = min(trie[cur].mn,ind);
        }
    }

    int get(int x,int k){
        int ans = inf;
        int cur = 0,i;
        for(i = 31; i >= 0; i--){
            int b = (x >> i) & 1;
            int kb = (k >> i) & 1;
            // cerr << b << ' ' << kb << '\n';
            if(!kb){
                if(trie[cur].nxt[!b] != -1) ans = min(ans,trie[trie[cur].nxt[!b]].mn);
                if(trie[cur].nxt[b] == -1) break;
                cur = trie[cur].nxt[b];
            }
            else{
                if(trie[cur].nxt[!b] == -1) break;
                cur = trie[cur].nxt[!b];
            }
        }
        if(i < 0) ans = min(ans,trie[cur].mn);
        return ans;
    }
};

void solve() {
    int n,k;
    cin >> n >> k;
    int prv = 0;
    Trie trie;
    trie.insert(0,0);
    int st,ln = 0;
    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        a ^= prv;
        prv = a;
        int now = i-trie.get(a,k);
        // cerr << now << ' ';
        if(ln < now){
            ln = now;
            st = i-now+1;
        }
        trie.insert(a,i);
    }
    cout << st << ' ' << ln << '\n';
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void solve()':
xor.cpp:77:19: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     cout << st << ' ' << ln << '\n';
      |                   ^~~

• Subtask 1: 100 / 100