Submission #1283935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283935		icy_	XOR (IZhO12_xor)	C++20	Compilation error	0 ms	0 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define hiken ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define fs first
#define sc second
#define ll long long
#define int long long
#define ld long double
#define vec vector
#define len(v) (int)v.size()
#define msbll(x) (63 - __builtin_clzll(x))
#define msbint(x) (31 - __builtin_clz(x))
#define lsbll(x) (__builtin_ctzll(x))
#define lsbint(x) (__builtin_ctz(x))
#define ones_count(x) (__builtin_popcount(x))
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define clr(a, x) memset(a, x, sizeof(a))
#define LOGB(base, x) (log(x) / log(base))

template <class T>
ostream &operator<<(ostream &out, vec<T> &A)
{
    for (auto &x : A)
        out << x << ' ';
    return out;
}

template <class T>
istream &operator>>(istream &in, vec<T> &A)
{
    for (auto &x : A)
        in >> x;
    return in;
}

template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using multiOrdered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define dbg(...) 42
#endif

void File()
{
#ifndef ONLINE_JUDGE
    freopen("feast.in", "r", stdin);
    freopen("feast.out", "w", stdout);
#endif
}
#define File File();

int di[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, -1, -1, 1};

ll lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

ostream &operator<<(ostream &os, __int128 n)
{
    if (n == 0)
        return os << '0';
    char buf[64];
    int i = 0;
    while (n > 0)
    {
        buf[i++] = (char)(n % 10 + '0');
        n /= 10;
    }
    while (i--)
        os << buf[i];
    return os;
}

istream &operator>>(istream &is, __int128 &n)
{
    string s;
    is >> s;
    n = 0;
    for (char c : s)
    {
        if ('0' <= c && c <= '9')
        {
            n = 10 * n + (c - '0');
        }
    }
    return is;
}

// assert
// #define NDEBUG
// #include <cassert>

//             Great things are done by a series of small things brought together.  ඞ
/*-----------------------------------------------------------------------------------------------------*/

const ll mod = (ll)(1e16 + 7);
const ll oo = 1e9 + 1;
const int N = 1e7;

struct node
{
    int child[2]{};
    int freq;

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

struct Trie
{
    vec<node> trie;

    Trie()
    {
        trie.clear();
        newnode();
    }

    int newnode()
    {
        trie.emplace_back();
        return len(trie) - 1;
    }

    void insert(int x)
    {
        int cur{};

        for (int i = 31; i >= 0; i--)
        {
            int bit = x >> i & 1;

            if (!trie[cur][bit])
                trie[cur][bit] = newnode();

            cur = trie[cur][bit];
            trie[cur].freq++;
        }
    }

    int sz(int x)
    {
        return trie[x].freq;
    }

    int get(int r)
    {
        int cur{}, res{};

        for (int i = 31; i >= 0; i--)
        {
            int bit = r >> i & 1;

            if (sz(trie[cur][bit ^ 1]))
            {
                cur = trie[cur][bit ^ 1];
                res ^= 1ll << i;
            }
            else
            {
                cur = trie[cur][bit];
            }
        }

        return res;
    }
};

void solve()
{
    int n, x;
    cin >> n >> x;

    vec<int> v(n + 1, 0);
    Trie jasper;
    jasper.insert(0);

    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        v[i] ^= v[i - 1];
    }

    map<int, int> mp;
    mp[0] = 0;

    /// index and length
    pair<int, int> ans{};

    for (int i = 1; i <= n; i++)
    {
        // l ^ r = g

        int g = jasper.get(v[i]);

        if (g >= x)
        {
            int l = g ^ v[i];
            int ind = mp[l];
            if (i - ind > ans.sc)
                ans = {ind + 1, i - ind};
        }

        jasper.insert(v[i]);

        // insert the smallest index that carry the same value of the v[i]
        if (mp.find(v[i]) == mp.end())
            mp[v[i]] = i;
    }

    cout << ans.fs << ' ' << ans.sc << endl;
}

signed main()
{
    hiken;

    auto start = chrono::high_resolution_clock::now();

    int t = 1;
    // cin >> t;
    // File;

    while (t--)
    {
        solve();
    }

    // auto end = chrono::high_resolution_clock::now();

    // cerr << fixed << setprecision(5);
    // cerr << "Execution time: " << chrono::duration_cast<chrono::duration<double>>(end - start).count() << " seconds" << endl;
}

Compilation message (stderr)

xor.cpp:48:10: fatal error: debug.h: No such file or directory
   48 | #include "debug.h"
      |          ^~~~~~~~~
compilation terminated.