Submission #1070894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070894		andrewp	XOR (IZhO12_xor)	C++17	0 / 100	22 ms	132444 KiB

xor

//Dedicated  my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n'; 

const int N = 250002;
const int L = 45; 
int n, x, v = 1, a[N], t[N * L][2], val[N * L];
  
void add(int s, int j) {
    int c = 0; 
    for (int i = L - 1; i >= 0; i--) {
        int st = (s >> i) & 1;
        if (t[c][st] == -1) 
            t[c][st] = v++;
        c = t[c][st], val[c] = min(val[c], j); 
    }
}

int query(int s) { 
    int ret = n + 1, c = 0, st1, st2;
    for (int i = L - 1; i >= 0; i--) {
        int st1 = (s >> i) & 1, st2 = (x >> i) & 1;
        if (st2) {
            if (st1) {
                if (t[c][0] == -1) 
                    break;
                c = t[c][0];
            } else {
                if (t[c][1] == -1) 
                    break;
                c = t[c][1]; 
            }
        } else {
            if (st1) {
                if (t[c][0] != -1) 
                    ret = min(ret, val[t[c][0]]);
                c = t[c][1];
            } else {
                if (t[c][1] != -1) 
                    ret = min(ret, val[t[c][1]]);
                c = t[c][0];
            }
        }
    }
    return ret;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr); 

    cin >> n >> x; 
    --x; 
    memset(t, -1, sizeof(t)); 
    memset(val, n + 1, sizeof(val)); 
    for (int i = 1; i <= n; i++)  
        cin >> a[i];  
    add(0, 0);
    int l = 0, r = 0, ps = 0;
    for (int i = 1; i <= n; i++) {
        ps ^= a[i];
        add(ps, i);
        int upd = query(ps);
        if (i - upd > r) 
            l = upd, r = i - upd;
        else if (upd == r) 
            l = min(l, upd);
    }
    l++;
    cout << l << ' ' << r << '\n'; 
    return 0;   
}

Compilation message (stderr)

xor.cpp: In function 'int query(int)':
xor.cpp:27:29: warning: unused variable 'st1' [-Wunused-variable]
   27 |     int ret = n + 1, c = 0, st1, st2;
      |                             ^~~
xor.cpp:27:34: warning: unused variable 'st2' [-Wunused-variable]
   27 |     int ret = n + 1, c = 0, st1, st2;
      |                                  ^~~

• Subtask 1: 0 / 100