제출 #1146779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146779		halzoom	XOR (IZhO12_xor)	C++20	100 / 100	123 ms	66212 KiB

xor

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
#define ll long long
#define int long long
#define double long double

void UwU() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

//void fileIO() {
//#ifndef ONLINE_JUDGE
//    freopen("Input.txt", "r", stdin);
//    freopen("Output.txt", "w", stdout);
//#endif
//}


const ll N = 1e5 + 5;
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll inf = 1e18;
const double EPS = 1e-4;

struct Trie {
private:
    struct Node {
        int child[2]{};
        int cnt = 0, minIDX = inf;

        int &operator[](int x) {
            return child[x];
        }
    };

    vector<Node> node;
public:
    Trie() {
        node.emplace_back();
    }

    int newNode() {
        node.emplace_back();
        return node.size() - 1;
    }

    int sz(int x) {
        return node[x].cnt;
    }

    int M = 30;

    void update(int x, int op, int idx) {
        int cur = 0;
        for (int i = M - 1; i >= 0; --i) {
            int c = x >> i & 1;
            if (node[cur][c] == 0) {
                node[cur][c] = newNode();
            }
            cur = node[cur][c];
            node[cur].cnt += op;
            node[cur].minIDX = min(idx, node[cur].minIDX);
        }
    }

    int query(int t, int x) {
        int cur = 0, res = inf, ret = inf;
        for (int i = M - 1; i >= 0; --i) {
            int ct = (t >> i) & 1;
            int cx = (x >> i) & 1;
            if (sz(sz(node[cur][ct ^ cx])) == 0) {
                res = inf;
                break;
            }
            if (cx == 0 and sz(node[cur][!ct])) {
                ret = min(ret, node[node[cur][!ct]].minIDX);
            }
            cur = node[cur][ct ^ cx];
            res = node[cur].minIDX;
        }
        return min(ret, res);
    }
};

void solve() {
    int n, X;
    cin >> n >> X;
    Trie trie;
    trie.update(0, 1, 0);
    int prefix = 0;
    int l = 0, k = 0;
    for (int i = 1, t; i <= n; ++i) {
        cin >> t;
        prefix ^= t;
        int x = trie.query(prefix, X);
        if (i - x > k) {
            k = i - x;
            l = x + 1;
        }
        trie.update(prefix, 1, i);
    }

    cout << l << ' ' << k;
}

// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

signed main() {
    UwU();
//    fileIO();

    int test = 1;
//    cin >> test;

    for (int i = 1; i <= test; ++i) {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100