Submission #685640

#	Time	Username	Problem	Language	Result	Execution time	Memory
685640		Ronin13	XOR (IZhO12_xor)	C++14	100 / 100	482 ms	115640 KiB

xor

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

vector <int> trie;
vector <vector <int> > children;
vector <int> dp;
int cur = 0;

int make_node(){
    trie.pb(cur);
    vector <int> vv;
    vv.assign(2, -1);
    children.pb(vv);
    dp.pb(1e9 + 1);
    return cur++;
}

int add(bitset <31> bt, int i, int cur, int j){
    if(j == -1){
        dp[cur] = min(dp[cur], i);
        return dp[cur];
    }
    int x = bt[j];
    if(children[cur][x] == -1){
        children[cur][x] = make_node();
    }
    dp[cur] = min(dp[cur], add(bt, i, children[cur][x], j - 1));
    return dp[cur];
}


int getans(bitset <31> x, bitset <31>y, int cur, int j){
    if(j == -1){
        return dp[cur];
    }
    if(x[j] == 0){
        int v = y[j] ^ 1;
        int ans = 1e9 + 1;
        if(children[cur][v] != -1)
            ans = dp[children[cur][v]];
        if(children[cur][y[j]] != -1){
            ans = min(ans, getans(x, y, children[cur][y[j]], j - 1));
        }
        return ans;
    }
    int v = y[j] ^ 1;
    if(children[cur][v] == -1) return 1e9 + 1;
    return getans(x, y, children[cur][v], j - 1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    make_node();
    int n; cin >> n;
    int X; cin >> X;
    int pref[n + 1];
    pref[0] = 0;
    add(0, 0, 0, 30);
    int v = 0;
    int l;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        pref[i] = pref[i - 1] ^ x;
        int p = getans(X, pref[i], 0, 30);
        if(p != 1e9 + 1){
            if(i - p > v)
                v = i - p, l = p + 1;
        }
        add(pref[i], i, 0, 30);
    }
    cout << l << ' ' << v;
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:79:18: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     cout << l << ' ' << v;
      |                  ^~~

• Subtask 1: 100 / 100