Submission #1153662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153662		Peti4	XOR (IZhO12_xor)	C++20	100 / 100	127 ms	25432 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 st(int u){return trie[u].st;}

    int query(int x, const int t)
    {
        int u = 0, ans;

        int tmp = inf;
        for (int i = M-1; ~i; --i)
        {
            bool bx = x >> i & 1;
            bool bt = t >> i & 1;

            if (bt)
            {
                if (!trie[u][!bx]) return tmp;
                u = trie[u][!bx];
            }
            else
            {
                if (trie[u][1^bx]) tmp = min(tmp, st(trie[u][1^bx]));
                u = trie[u][bx];
            }
            ans = trie[u].st;
        }
        return min(ans, tmp);

    }
};

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: 100 / 100