Submission #768327

#	Time	Username	Problem	Language	Result	Execution time	Memory
768327		DylanSmith	XOR (IZhO12_xor)	C++17	100 / 100	155 ms	28340 KiB

xor

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

typedef struct node {
    int l, r; int mn;
    node() {
        l = r = -1; mn = INT_MAX;
    }
} node;

vector<node> tree(1);

int add(int n) {
    int cur = 0;
    for (int i = 29; i >= 0; i--) {
        if ((n & 1 << i) == 0) {
            if (tree[cur].l == -1) {
                tree[cur].l = sz(tree);
                tree.emplace_back();
            }
            cur = tree[cur].l;
        } else {
            if (tree[cur].r == -1) {
                tree[cur].r = sz(tree);
                tree.emplace_back();
            }
            cur = tree[cur].r;
        }
    }
    return cur;
}

void solve() {
    int N, K; cin >> N >> K;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) cin >> arr[i];
    tree[add(0)].mn = -1;
    vector<int> pre(N);
    for (int i = 0; i < N; i++) {
        pre[i] = arr[i];
        pre[i] ^= i == 0 ? 0 : pre[i - 1];
        int u = add(pre[i]);
        tree[u].mn = min(tree[u].mn, i);
    }
    for (int i = sz(tree) - 1; i >= 0; i--) {
        if (tree[i].l != -1) tree[i].mn = min(tree[i].mn, tree[tree[i].l].mn);
        if (tree[i].r != -1) tree[i].mn = min(tree[i].mn, tree[tree[i].r].mn);
    }
    vector<int> res = {0, 0};
    for (int i = 0; i < N; i++) {
        int cur = 0;
        int mn = INT_MAX;
        for (int j = 29; j >= 0; j--) {
            if (cur == -1) continue;
            if ((K & 1 << j) == 0) {
                if ((pre[i] & 1 << j) == 0) {
                    if (tree[cur].r != -1) mn = min(mn, tree[tree[cur].r].mn);
                    cur = tree[cur].l;
                } else {
                    if (tree[cur].l != -1) mn = min(mn, tree[tree[cur].l].mn);
                    cur = tree[cur].r;
                }
            } else {
                if ((pre[i] & 1 << j) == 0) {
                    cur = tree[cur].r;
                } else {
                    cur = tree[cur].l;
                }
            }
        }
        if (cur != -1) mn = min(mn, tree[cur].mn);
        if (mn == INT_MAX) continue;
        if (mn < i) {
            if (i - mn > res[1]) {
                res = {mn, i - mn};
            }
        }
    }
    cout << (res[0] + 2) << " " << res[1] << "\n";
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    //setIO("c");
    solve();
 
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void setIO(std::string)':
xor.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100