Submission #1171156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171156		mostafa__fouad	XOR (IZhO12_xor)	C++20	0 / 100	1 ms	328 KiB

xor

#include<bits/stdc++.h>
#define ll long long
// #define int ll
using namespace std;
const int N = 5e5 + 5, M = 5e4 + 2, MOD = 1e9 + 7, root = 320;
#define deb(x) cout<<#x<<"="<<x<<endl;
#define F first
#define S second

struct Node
{
    int nxt[2]{};
    int ed{};
    int freq{};
    int sum{};


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

struct Trie
{
    vector<Node> trie;

    int newNode()
    {
        trie.emplace_back();
        return trie.size() - 1;
    }

    Trie()
    {
        newNode();
    }


    void add(const int x, int added_idx, int idx, int bit)
    {
        if (bit < 0)
        {
            trie[idx].ed = max(trie[idx].ed, added_idx);
            trie[idx].freq++;
            return;
        }
        bool f = x & (1ll << bit);
        if (!trie[idx][f])trie[idx][f] = newNode();
        trie[trie[idx][f]].freq++;
        add(x, added_idx, trie[idx][f], bit - 1);
        trie[idx].ed = max({trie[idx].ed, trie[trie[idx][f]].ed, trie[trie[idx][f ^ 1]].ed});
    }

    int query(int num, int x)
    {
        int idx{}, ret{};
        for (int j = 63; j >= 0; j--)
        {
            bool f = num & (1ll << j), xx = x & (1ll << j);
            if (xx)
            {
                if (!trie[trie[idx][f ^ 1]].freq)return 0;
                idx = trie[idx][f ^ 1];
            }
            else
            {
                if (trie[trie[idx][f ^ 1]].freq)ret = max(ret, trie[trie[idx][f ^ 1]].ed);
                if (trie[trie[idx][f]].freq)idx = trie[idx][f];
                else return ret;
            }
        }
        return max(ret, trie[idx].ed);
    }
} t;

void solve()
{
    int n, x;
    cin >> n >> x;
    int a[n];
    for (int i = 0; i < n; i++)cin >> a[i];
    int suf{};
    t.add(suf, n, 0, 63);
    int ansl = -1, ansr = -1, len{};
    for (int i = n - 1; i >= 0; i--)
    {
        suf ^= a[i];
        int tmp = t.query(suf, x);
        if (tmp - i + 1 >= len)
        {
            len = tmp - i + 1;
            ansl = i;
            ansr = tmp - i;
        }
        t.add(suf, i, 0, 63);
    }
    cout << ansl + 1 << " " << ansr;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // #ifndef ONLINE_JUDGE
    //     freopen("output.txt", "w", stdout);
    //     freopen("input.txt", "r", stdin);
    // #endif

    int tt = 1;
    // cin >> tt;
    for (int i = 0; i < tt; i++)
    {
        solve();
        // cout << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 100