Submission #1153651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153651		Peti4	XOR (IZhO12_xor)	C++20	0 / 100	2094 ms	1208 KiB

xor

#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()
#define vi vector<int>

#define pii pair<int, int>
#define pll pair<ll, ll>


const int N = 1e5+5, MOD = 1e9+7;


const int M = 30, inf = INT_MAX;

struct Node
{
    int ch[2]{}, st{};
    int &operator[](int 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 ndx)
    {
        int u = 0;
        for (int i = M-1; ~i; --i)
        {
            bool b = x >> i & 1;
            if (!trie[u][b])
            {
                trie[u][b] = newNode();
                u = trie[u][b];
                trie[u].st = ndx;
            }
            else u = trie[u][b];
        }
    }

    int query(int x, const int trg, int u = 0, int i = M-1, int xr = 0)
    {
        if (!~i)
        {
            if (xr >= trg) return trie[u].st;
            return inf;
        }
        bool bx = x >> i & 1;
        int a = inf, b = inf;
        if (trie[u][0])
            a = max(trie[u].st, query(x, trg, trie[u][0], i-1, xr | (bx * (1<<i))));
        if (trie[u][1])
            b =  max(trie[u].st, query(x, trg, trie[u][1], i-1, xr | ((bx^1) * (1<<i))));
        return min(a, b);
    }
};

void solve()
{
    int n, x; cin >> n >> x;
    Trie trie;
    int a = 0, b = 0, xr = 0;
    trie.insert(0, 0);
    if (xr >= x) a = b = 1;

    for (int i = 1; i <= n; i++)
    {
        int e; cin >> e;
        xr ^= e;

        int ans = trie.query(xr, x);
        if (i-ans > b) a = ans+1, b = i-ans;
        trie.insert(xr, i);
    }
    cout << a << ' ' << b << endl;
}


signed main() {
    // ifstream cin("c.in");
    // ofstream cout("c.out");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
}

• Subtask 1: 0 / 100