제출 #1325851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325851		muzan	XOR (IZhO12_xor)	C++20	100 / 100	98 ms	34284 KiB

xor

#include <bits/stdc++.h>
using namespace std;

const int L = 30;
struct Trie {
    struct node : array<int, 2> {
        int cnt{};
        int mx = -1;
    };
    vector<node> tr;
    Trie() : tr(2) { }

    int nxt(int x, int c) {
        if(tr[x][c]) return tr[x][c];
        tr.emplace_back();
        return tr[x][c] = int(tr.size()) - 1;
    }

    void add(int v, int j) {
        int x = 1;
        for(int i = L - 1; i >= 0; i--) {
            tr[x].cnt++;
            tr[x].mx = max(tr[x].mx, j);
            x = nxt(x, v >> i & 1);
        }
        tr[x].cnt++;
        tr[x].mx = max(tr[x].mx, j);
    }

    int query(int v, int k) {
        int x = 1, mx = -1;
        for(int i = L - 1; i >= 0; i--) {
            int xor0 = tr[x][v >> i & 1];
            int xor1 = tr[x][v >> i & 1 ^ 1];

            if(!(k >> i & 1)) {
                x = xor0;
                mx = max(mx, tr[xor1].mx);
            }
            else {
                x = xor1;
            }
        }
        return max(mx, tr[x].mx);
    }
};

void TC() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int &i : a) cin >> i;

    int bestI = 0, bestK = 0;
    int suf = 0;
    Trie tr;
    tr.add(suf, n);
    for(int i = n - 1; i >= 0; i--) {
        suf ^= a[i];
        tr.add(suf, i);
        int j = tr.query(suf, k);
        if(j - i >= bestK) bestK = j - i, bestI = i;
    }
    cout << bestI + 1 << ' ' << bestK << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int tc = 1;
//    cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        TC();
    }
//    cerr << clock() / 1000.0 << " Secs";
    return 0;
}

• Subtask 1: 100 / 100