Submission #1302170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302170		slimshady45	XOR (IZhO12_xor)	C++20	100 / 100	227 ms	145028 KiB

xor

// template taken from Striver_79
// Remember you were also a novice when you started
// hence never be rude to anyone who wants to learn something
// Never open a ranklist untill and unless you are done with solving problems, wastes 3/4 minutes
// Donot treat CP as a placement thing, love it and enjoy it, you will succeed for sure.
// The goal is to solve problems most efficiently not just barely

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

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int mod = 1e9 + 7;
#define int long long
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vector<int>> vii;
typedef vector<pair<int, int>> vpi;
typedef pair<int, int> pi;

// ------------------ Debug Utilities ------------------
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v)
{
    bool first = true;
    string res = "{";
    for (auto &x : v)
    {
        if (!first)
            res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef ONLINE_JUDGE
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
// ------------------------------------------------------

void myerase(ordered_set &t, int v)
{
    int rank = t.order_of_key(v);
    ordered_set::iterator it = t.find_by_order(rank);
    if (it != t.end())
        t.erase(it);
}

int power(long long x, unsigned int y, int p = 1e9 + 7)
{
    int res = 1;
    x %= p;
    if (x == 0)
        return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y >>= 1;
        x = (x * x) % p;
    }
    return res;
}

int gcdExtended(int a, int b, int *x, int *y)
{
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}

int modInverse(int b, int m)
{
    int x, y;
    int g = gcdExtended(b, m, &x, &y);
    if (g != 1)
        return -1;
    return (x % m + m) % m;
}

int modDivide(int a, int b, int m)
{
    a %= m;
    int inv = modInverse(b, m);
    if (inv == -1)
        return -1;
    return (inv * a) % m;
}

ll accurateFloor(ll a, ll b)
{
    ll val = a / b;
    while (val * b > a)
        val--;
    return val;
}
struct TrieNode
{
    vector<TrieNode *> children;
    bool isEnd;
    int idx;
    TrieNode()
    {
        isEnd = false;
        idx = 1e9;
        children.assign(2, nullptr);
    }
};
class Trie
{
    TrieNode *root;
    int subquery(TrieNode *root, int idx, int x, int k)
    {
        if (!root)
        {
            return 1e9;
        }
        if (idx < 0)
        {
            return root->idx;
        }

        int nx = x ^ (1LL << idx);
        int xbit = (x >> idx) & 1;
        int kbit = (k >> idx) & 1;
        // debug(xbit,kbit,k,x);
        if (kbit == 0)
        {
            int ans = 1e9;
            if (root->children[xbit ^ 1])
            {
                ans = min(ans, root->children[xbit ^ 1]->idx); // definitely greater than >=k now
            }
            ans = min(ans, subquery(root->children[xbit], idx - 1, x, k));
            return ans;
        }
        else
        {
            if (root->children[xbit ^ 1])
            {
                return subquery(root->children[xbit ^ 1], idx - 1, x, k);
            }
        }
        return 1e9;
    }

public:
    Trie()
    {
        root = new TrieNode();
    }
    void insert(int p, int idx)
    {
        TrieNode *curr = root;
        for (int i = 29; i >= 0; i--)
        {
            int bit = (p >> i) & 1ll;
            if (!curr->children[bit])
            {
                TrieNode *temp = new TrieNode();
                curr->children[bit] = temp;
            }
            curr = curr->children[bit];
            curr->idx = min(idx, curr->idx);
        }
        curr->isEnd = true;
    }
    int query(int p, int l)
    {
        TrieNode *curr = root;
        return subquery(curr, 29, p, l);
    }
};
void solve()
{
    ll n;
    cin >> n;
    ll k;
    cin >> k;
    vi arr(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    Trie *t = new Trie();
    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        pref[i] = pref[i - 1] ^ arr[i - 1];
    }
    t->insert(0, 0);
    int ans = -1e10;
    int idxans=1e9;
    for (int i = 1; i <= n; i++)
    {
        int lidx = t->query(pref[i], k);
        int nans=i-lidx;
        // debug(ans,nans);
        if(nans>ans)
        {
            ans=nans;
            idxans=lidx+1;
        }
        else if(nans==ans)
        {
            idxans=min(idxans,lidx+1);
        }
        t->insert(pref[i],i);
    }
    cout<<idxans<<" "<<ans<<"\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100