제출 #1281704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281704		ahmedkhaled	XOR (IZhO12_xor)	C++20	100 / 100	183 ms	68288 KiB

xor

#include <iostream>
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define Ahmed cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), \
cout.sync_with_stdio(0);
#define ll long long
#define int ll
#define all(v) v .begin(), v.end()
#define allRev(v) v.rbegin(), v.rend()
#define el '\n'
#define pii pair<int, int>
#define pll pair<ll, ll>
#define popcnt(n) __builtin_popcount(n)

#define ordered_set tree<ll, null_type,less<ll>, \
rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type, less_equal<ll>, rb_tree_tag, \
tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

//const ll mod = 998244353;
const ll mod = 1e9 + 7;
const int N = 5 * 1e5 + 10, Log = 22;
const ll inf = 1e18, neg = -1e18;
const double pi = 3.14159265358979323846;
char direction[4] = {'R', 'L', 'D', 'U'};
//           U   D  R   L
int di[8] = {0, +0, 1, -1, -1, -1, +1, 1};
int dj[8] = {1, -1, 0, +0, -1, +1, -1, 1};

void start() {
    Ahmed
//    cout << fixed << setprecision(12);
//    cin.ignore();
//    getline(cin, variable);
// #ifndef ONLINE_JUDGE
//     freopen("in.txt", "r", stdin);
//     freopen("out.txt", "w", stdout);
// #endif
}

struct Node {
    int ch[2]{};
    int freq = 0, minIdxAt = inf;///minimum index of this prefix

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

struct Trie {
    vector<Node> trie;

    Trie() {
        newNode();
    }

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

    void insert(int x, int op, int idx) {
        int u = 0;
        for (int i = 31; i >= 0; --i) {
            int bit = x >> i & 1;
            if (!trie[u][bit])
                trie[u][bit] = newNode();
            trie[u].minIdxAt = min(trie[u].minIdxAt, idx);
            u = trie[u][bit];
            trie[u].freq += op;
        }
        trie[u].minIdxAt = min(trie[u].minIdxAt, idx);
    }

    ll count(int r, int k) {
        /// count how many l's such l ^ r >= k
        ll u = 0, ret = inf;
        for (int i = 31; i >= 0; --i) {
            int rBit = r >> i & 1, kBit = k >> i & 1, dir = rBit ^ kBit;
            if (!kBit and trie[u][!rBit])
                ret = min(ret, trie[trie[u][!rBit]].minIdxAt);
            u = trie[u][dir];
            if (u == 0) return ret;
        }
        return min(ret, trie[u].minIdxAt);
    }
};


void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> pre(n + 1);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pre[i + 1] = pre[i] ^ a;
    }
    Trie trie;
    trie.insert(0, 1, 0);
    ll idx{}, k{};
    for (int i = 1; i <= n; ++i) {
        int ret = trie.count(pre[i], x);
        if (ret != inf and k < i - ret) {
            k = i - ret;
            idx = ret + 1;
        }
        trie.insert(pre[i], 1, i);
    }
    cout << idx << ' ' << k << el;
}

int32_t main() {
    start();

    int t = 1;
//    cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 100 / 100