Submission #1295961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295961		alyyy	XOR (IZhO12_xor)	C++20	100 / 100	148 ms	57744 KiB

xor

// #define OJ
// #define TEST


#include <bits/stdc++.h>
using namespace std;
#ifdef OJ
    #pragma GCC target("avx2")
    #pragma GCC optimize("O3")
    #pragma GCC optimize("unroll-loops")
#endif
#ifndef ALY
#define ALY
    static int __star = []{
        ios_base::sync_with_stdio(0);
        cin.tie(NULL),cout.tie(NULL);
        return 0;
    }();
    using ll = long long;
    using ull = unsigned long long;
    using uint = unsigned int;
    using u8 = uint8_t;
    using u16 = uint16_t;
    using u32 = uint32_t;
    using u64 = uint64_t;
    using in8 = uint8_t;
    using in16 = uint16_t;
    using in32 = uint32_t;
    using in64 = uint64_t;
    using db = long double;
    using str = string;
    using pi = pair<int,int>;
    using pl = pair<ll,ll>;
    #define mp make_pair
    #define f first
    #define s second
    #define vcA template<class A
    vcA> using V = vector<A>;
    vcA> using MAT = V<V<A>>;
    using vi = V<int>;
    using vb = V<bool>;
    using vl = V<ll>;
    using vd = V<db>;
    using vs = V<str>;
    using vpi = V<pi>;
    using vpl = V<pl>;
    using mat = V<vi>;
    using matl = V<vl>;
    #define sz(x) int((x).size())
    #define bg(x) begin(x)
    #define rbg(x) rbegin(x)
    #define ed(x) end(x)
    #define all(x) begin(x), end(x)
    #define pfr(x, a) begin(x), begin(x) + a
    #define rall(x) x.rbegin(), x.rend()
    #define srt(x) sort(all(x))
    #define nth(x, a) nth_element(pfr(x, a), ed(x))
    #define npp(x) next_permutation(all(x))
    #define shl(x, a) ((x) << (a))
    #define shr(x, a) ((x) >> (a))
    #define pb push_back
    #define pf push_front
    #define eb emplace_back
    #define em empty()
    #define ft front()
    #define bk back()
    #define ppb pop_back()
    #define ppf pop_front()
    #define pp pop()
    #define tp top()
    #define lb lower_bound
    #define ub upper_bound
    #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
    #define F0R(i, a) FOR(i, 0, a)
    #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); --i)
    #define R0F(i, a) ROF(i, 0, a)
    #define xtime(a) F0R(_, a)
    #define each(a, x) for(auto& a : x)
    static constexpr int MOD = 1'000'000'007;
    static constexpr int MD2 = 1'000'000'009;
    static constexpr int ALT = 998'244'353;
    static constexpr u64 B1 = 911'382'323;
    static constexpr u64 B2 = 972'663'749;
    static constexpr ll LMX = 1e18;
    static constexpr int XDIR[4] {1, 0, -1, 0}, YDIR[4] {0, 1, 0, -1};
    template<class P> using pqpl = priority_queue<P, vector<P>, greater<P>>;
    template<class P> using pqpg = priority_queue<P, vector<P>, less<P>>;
    constexpr int pct(int x) { return __builtin_popcount(x); }
    constexpr int ctz(int x) { return __builtin_ctz(x); }
    constexpr int clz(int x) { return __builtin_clz(x); }
    constexpr int pctll(ll x) { return __builtin_popcountll(x); }
    constexpr int ctzll(ll x) { return __builtin_ctzll(x); }
    constexpr int clzll(ll x) { return __builtin_clzll(x); }
    ll ceill(ll a, ll b) { return (a + b - 1) / b; }
    vcA> void printvec(V<A>&a) { each(v,a) { cout << v << ' '; } cout << '\n'; }
    // binstr
    template<typename C>
    void meow(C num) { for(int bits = sizeof(num) * 8; bits--; num >>= 1) cout << !!(num & 1); cout << '\n'; }
    // pos of msb, msb(0) = -1, msb(2) = 1, msb(1) = 0, etc.
    template<typename C>
    int woof(C n) {
        if(!n) return -1;
        switch(sizeof(C)) {
            case 1: return 7 - clz(static_cast<uint>(n) << 24);
            case 2: return 15 - clz(static_cast<uint>(n) << 16);
            case 4: return 31 - clz(static_cast<uint>(n));
            case 8: return 63 - clzll(static_cast<ull>(n));
        }
        return -1;
    }
    // for coordinate comp
    template<typename T>
    int v2i(V<T>& A, T val) { return int(lower_bound(all(A), val) - bg(A)); }
#endif


/*
    first occurrence of prefix
    same rules for choosing nxt as >= k

    suf ^ pre >= k

    :.
    si & ki   | ->0
    si & !ki  | +0, ->1
    !si & ki  | ->1
    !si & !ki | +1, ->0
*/


struct node {
    int id = INT_MAX;
    node* nxt[2]{nullptr};
};


struct trie {
    node* root;
    trie() : root(new node) { ins(0, 0); }

    void ins(int x, int idx) {
        node* cur = root;
        for(int i = shl(1, 29); i; i >>= 1) {
            auto& nxt = cur->nxt[!!(x & i)];
            if(!nxt) nxt = new node{idx, nullptr, nullptr};
            cur = nxt;
        }
    }

    int get(node* cur) {
        return cur ? cur->id : INT_MAX;
    }

    int quer(int x, int k) {
        node* cur = root;
        int ret = INT_MAX;
        // si & ki   | ->0
        // si & !ki  | +0, ->1
        // !si & ki  | ->1
        // !si & !ki | +1, ->0
        for(int i = shl(1, 29); i; i >>= 1) {
            int xi = !!(x & i), ki = !!(k & i), nxt = 0;
            if(xi && !ki) {
                ret = min(ret, get(cur->nxt[0]));
                nxt = 1;
            } else if(!xi && ki) {
                nxt = 1;
            } else if(!xi && !ki) {
                ret = min(ret, get(cur->nxt[1]));
                nxt = 0;
            }
            cur = cur->nxt[nxt];
            if(!cur) return ret;
        }
        return min(ret, cur->id);
    }
};


int main() {
#ifdef TEST
#else
    int n, k;
    cin >> n >> k;
    vi A(n); each(i, A) cin >> i;
    trie T;

    int sum = 0, ri = INT_MAX, rk = 0;
    F0R(i, n) {
        sum ^= A[i];
        int q = T.quer(sum, k);
        if(q != INT_MAX) {
            int ck = i - q + 1;
            if(ck == rk) ri = min(ri, q);
            if(ck > rk) rk = ck, ri = q;
        }
        T.ins(sum, i + 1);
    }
    // since ri represents the end 1-indexed index of
    // the prefix that gets removed, ri + 1 is the begin
    // of the contig of length rk that is actually used
    cout << ri + 1 << ' ' << rk << '\n';
#endif
    return 0;
}

• Subtask 1: 100 / 100