제출 #1146666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146666		Braabebo10	XOR (IZhO12_xor)	C++20	100 / 100	122 ms	68192 KiB

xor

#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll M = 32;

struct node {
    ll sz = 0, mp[2]{}, id = 3e5;
    ll &operator[](ll i) {
        return mp[i];
    }
};

struct Trie {
    vector<node> trie;
    ll create() {
        trie.emplace_back();
        return trie.size() - 1;
    }

    Trie() {
        trie.clear();
        create();
    }

    void insert(ll x, ll idx) {
        ll u = 0;
        bitset<32> bits = x;
        for (ll i = M - 1; i >= 0; i--) {
            if (!trie[u][bits[i]])
                trie[u][bits[i]] = create();
            u = trie[u][bits[i]];
            trie[u].sz++;
            trie[u].id = min(trie[u].id, idx);
        }
    }

    ll get(ll x, ll k) {
        ll idx = 3e5, u = 0;
        bitset<32> bitx = x, bitk = k;
        for (ll i = M - 1; i >= 0; i--) {
            ll xr = bitx[i] ^ bitk[i];
            if (!bitk[i])
                idx = min(idx, trie[trie[u][!bitx[i]]].id);
            if (!trie[u][xr])return idx;
            u = trie[u][xr];
        }
        return min(trie[u].id, idx);
    }
};

int main() {
    baraa
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll &i: a)cin >> i;
    array<ll, 2> ans = {n + 1, n + 1};
    Trie tree;
    tree.insert(0, -1);
    for (ll i = 0; i < n; i++) {
        if (i)a[i] ^= a[i - 1];
        ll idx = tree.get(a[i], k) + 1;
        if (ans[1] - ans[0] < i - idx or (ans[1] - ans[0] == i - idx and idx < ans[0]))ans[0] = idx, ans[1] = i;
        tree.insert(a[i], i);
    }
    cout << ans[0] + 1 << ' ' << ans[1] - ans[0] + 1;
    return 0;
}

• Subtask 1: 100 / 100