Submission #1272862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272862		musanna47	XOR (IZhO12_xor)	C++20	100 / 100	75 ms	43784 KiB

xor

// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)

#include "bits/stdc++.h"

using namespace std;


#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)


template<typename T1, typename T2>
using P = pair<T1, T2>;
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using VVV = V<V<V<T>>>;
template<typename T>
using VVVV = V<V<V<V<T>>>>;


using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;
using vi = V<int>;
using vvi = VV<int>;
using vll = V<ll>;
using vvll = VV<ll>;
using vpii = V<pii>;
using vpll = V<pll>;


template<typename T>
void pout(T a, string sep = " ", string fin = "\n") {
    cout << a.first << sep << a.second << fin;
}

template<typename T>
void print(T &a, ll l, ll r, string sep = " ", string fin = "\n") {
    for (ll i = l; i <= r; i++)
        cout << a[i] << sep;
    cout << fin;
}

template<typename T>
void printPairs(T &a, ll l, ll r, string fin = "\n") {
    for (ll i = l; i <= r; i++)
        pout(a[i]);
    cout << fin;
}

template<typename T>
void printAll(T &a, string sep = " ", string fin = "\n") {
    for (auto &ele: a)
        cout << ele << sep;
    cout << fin;
}

template<typename T>
void printPairsAll(T &a, string fin = "\n") {
    for (auto &ele: a)
        pout(ele);
    cout << fin;
}

template<typename... Args>
void read(Args &... args) {
    ((cin >> args), ...);
}

template<typename... Args>
void out(Args... args) {
    ((cout << args << " "), ...);
}

template<typename... Args>
void outln(Args... args) {
    ((cout << args << " "), ...);
    cout << nl;
}

template<typename T>
void vin(T &a, ll l, ll r) {
    for (ll i = l; i <= r; i++)
        cin >> a[i];
}

template<typename T>
void makeUnique(T &a) {
    a.erase(unique(all(a)), a.end());
}


using bll = __int128;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.141592653589793;
const double EPS = 1e-12;


void prec() {

}

const int N = 250005;
int trie[N * 30][2], cnt[N * 30];
int n, k, tot = 0, mxLen = 0, start = INF;

struct Trie {
    void insert(int x, int idx) {
        int u = 0;
        REPB(i, 30, 0) {
            bool v = x & (1 << i);
            if (!trie[u][v])
                trie[u][v] = ++tot;
            u = trie[u][v];
            cnt[u] = min(cnt[u], idx);
        }
    }

    void query(int x, int idx) {
        int u = 0;
        REPB(i, 30, 0) {
            bool p = k & (1 << i);
            bool v = x & (1 << i);
            if (p) {
                if (!trie[u][!v])
                    return;
                u = trie[u][!v];
                continue;
            }
            if (trie[u][!v]) {
                int len = idx - cnt[trie[u][!v]];
                if (len > mxLen) mxLen = len, start = cnt[trie[u][!v]] + 1;
                else if (len == mxLen) start = min(start, cnt[trie[u][!v]] + 1);
            }
            if (!trie[u][v])
                return;
            u = trie[u][v];
        }
        int len = idx - cnt[u];
        if (len > mxLen) mxLen = len, start = cnt[u] + 1;
        else if (len == mxLen) start = min(start, cnt[u] + 1);
    }
} T;

void solve() {
    read(n, k);
    memset(cnt, 0x3f, sizeof cnt);

    int XOR = 0;
    T.insert(XOR, 0);
    REPF(i, 1, n) {
        int x;
        read(x);
        XOR ^= x;
        T.query(XOR, i);
        T.insert(XOR, i);
    }

    outln(start, mxLen);
}


signed main() {
    auto OJ = []() -> void {
#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
    };

    cin.tie(0)->sync_with_stdio(0);

    // OJ();

    // cout << fixed << setprecision(10);

    // prec();

    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; i++) {
        // cout << "Case " << i << ": ";
        solve();
        // cout << nl;
    }

    return 0;
}

• Subtask 1: 100 / 100