제출 #1138688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138688		salmakaram22222	XOR (IZhO12_xor)	C++20	0 / 100	2 ms	2880 KiB

xor

#include <bits/stdc++.h>

#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

#define ll long long
#define int long long
int const N = 3e5 + 5, M = 998244353;
int n, x, idx;
int tab[20][N], LG[N], pre[N];
vector<pair<int, int>> v;

void sparsetable() {
    for (int i = 2; i < N; ++i) {
        LG[i] = LG[i / 2] + 1;
    }

    for (int i = 1; i <= n; i++) {
        tab[0][i] = v[i - 1].second;
    }
    for (int i = 1; (1 << i) <= n; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            tab[i][j] = max(tab[i - 1][j], tab[i - 1][j + (1 << (i - 1))]);
        }
    }
}

int query(int l, int r) {
    int len = LG[r - l + 1];
    return max(tab[len][l], tab[len][r - ((1 << (x))) + 1]);
}

void dowork() {
    cin >> n >> x;
    map<int, int> mp;
    for (int i = 1, e; i <= n; ++i) {
        cin >> e;
        pre[i] = e ^ pre[i - 1];
        v.emplace_back(pre[i], i);
        mp[pre[i]] = i;
    }

    sort(v.begin(), v.end());
    sparsetable();

    int left = 0;//the left part for x : 101xxxx or 1010xxx
    int index{}, k = {};
    for (int i = 4; i >= 0; --i) {
        if (x & (1 << i)) {
            left |= (1 << i);
            continue;//a fixed way for prefl^prefr=x
        }
        //we need this bit to be one : prel^prer=1 so we ignore the other right part (as it will be greater than x for sure)
        left |= (1 << i);
        for (int j = 0; j < n; ++j) {
            int val = pre[j] ^ left;
            int emptyrightpart = (1 << i) - 1;
            int l = val - (val & emptyrightpart);//101xxxxx : 10100000
            int r = l + emptyrightpart;//101xxxxxx : 1011111111
            l = lower_bound(v.begin(), v.end(), make_pair(l, -1ll)) - v.begin();
            r = lower_bound(v.begin(), v.end(), make_pair(r + 1, -1ll)) - v.begin();
            r--;
            if (l <= r and l != (int) v.size()) {
                int mx = query(l + 1, r + 1);
                if (mx >= j + 1) {
                    if (mx - j > k) {
                        index = j + 1, k = mx - j;
                    }
                }
            }
        }
        //return it back
        left ^= (1 << i);
    }

    //for the fixed part prefl^prefr=x
    for (int i = 0; i < n; ++i) {
        int search = x ^ pre[i];
        int mx = mp[search];
        if (mx >= i + 1) {
            if (mx - i > k) {
                index = i + 1, k = mx - i;
            }
        }
    }

    cout << index << ' ' << k;
}

signed main() {
    Pc_champs
    int t = 1;
    //cin >> t;
    while (t--) {
        ++idx;
        dowork();
        cout << "\n";
    }
}

• Subtask 1: 0 / 100