oj.uz

Submission #685640

# Submission time Handle Problem Language Result Execution time Memory
685640 2023-01-24T17:59:06 Z Ronin13 XOR (IZhO12_xor) C++14
100 / 100
 482 ms 115640 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 16 ms 3468 KB Output is correct
6 Correct 20 ms 3612 KB Output is correct
7 Correct 21 ms 3696 KB Output is correct
8 Correct 22 ms 3848 KB Output is correct
9 Correct 174 ms 54312 KB Output is correct
10 Correct 180 ms 54652 KB Output is correct
11 Correct 185 ms 54348 KB Output is correct
12 Correct 199 ms 54432 KB Output is correct
13 Correct 202 ms 54524 KB Output is correct
14 Correct 184 ms 54668 KB Output is correct
15 Correct 184 ms 54544 KB Output is correct
16 Correct 168 ms 54444 KB Output is correct
17 Correct 464 ms 115612 KB Output is correct
18 Correct 467 ms 115640 KB Output is correct
19 Correct 482 ms 115620 KB Output is correct
20 Correct 468 ms 115568 KB Output is correct