Submission #898665

#	Time	Username	Problem	Language	Result	Execution time	Memory
898665		typ_ik	XOR (IZhO12_xor)	C++17	100 / 100	212 ms	87648 KiB

xor

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 3e5 + 128;
const int LOG = 31;
int n, x;
int a[N];

struct node {
    node* nxt[2];
    int min_id;
    node* p;

    node() {
        nxt[0] = nxt[1] = p = nullptr;
        min_id = N;
    }

    void upd() {
        if (nxt[0] != nullptr)
            min_id = min(min_id, nxt[0]->min_id);
        if (nxt[1] != nullptr)
            min_id = min(min_id, nxt[1]->min_id);
    }
};

node* root = new node();

void add(int val, int pos) {
    node* cur = root;

    for (int b = LOG - 1; b >= 0; b--) {
        bool v = ((val >> b) & 1);
        if (cur->nxt[v] == nullptr)
            cur->nxt[v] = new node(), cur->nxt[v]->p = cur;
        cur = cur->nxt[v];
    }

    cur->min_id = min(cur->min_id, pos);

    while (cur != nullptr)
        cur->upd(), cur = cur->p;
}

int get(int val) {
    node* cur = root;

    int ans = N;

    for (int b = LOG - 1; b >= 0 && cur != nullptr; b--) {
        bool v = ((x >> b) & 1);
        bool have = ((val >> b) & 1);
        if (!v && cur->nxt[have ^ 1] != nullptr)
            ans = min(ans, cur->nxt[have ^ 1]->min_id);
        cur = cur->nxt[have ^ v];
    }

    if (cur != nullptr)
        ans = min(ans, cur->min_id);

    return ans;
}

void solve() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] ^= a[i - 1];

    add(0, 0);

    int L = 0, R = -1;
    for (int i = 1; i <= n; i++) {
        add(a[i], i);
        int nl = get(a[i]);
        if (i - nl > R - L)
            L = nl, R = i;
    }

    cout << L + 1 << ' ' << R - L << '\n';
}

main() {
    boost;
    solve();
    return 0;
}

Compilation message (stderr)

xor.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main() {
      | ^~~~

• Subtask 1: 100 / 100