제출 #1171219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171219		mostafa__fouad	XOR (IZhO12_xor)	C++20	100 / 100	181 ms	84552 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
int mx, ans;

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{};
        for (int i = 63; i >= 0; i--)
        {
            bool f = x & (1ll << i);
            if (!trie[idx][f])trie[idx][f] = newNode(), trie[trie[idx][f]].ed = added_idx;
            idx = trie[idx][f];
        }
    }

    void query(int num, int x,int i)
    {
        int idx{};
        for (int j = 63; j >= 0; j--)
        {
            bool f = num & (1ll << j), xx = x & (1ll << j);
            if (f == xx and trie[idx][!f])
            {
                if (mx < i - trie[trie[idx][!f]].ed)
                {
                    mx = i - trie[trie[idx][!f]].ed;
                    ans = trie[trie[idx][!f]].ed + 1;
                }
            }
            if (!trie[idx][f])
            {
                return;
            }
            idx = trie[idx][f];
        }
        if (mx < i - trie[idx].ed)
        {
            mx = i - trie[idx].ed;
            ans = trie[idx].ed + 1;
        }
    }
} t;

void solve()
{
    int n, x;
    cin >> n >> x;
    int a[n + 1]{};
    t.add(0, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] ^= a[i - 1];

        t.add(a[i], i);
        t.query((a[i] ^ x), a[i], i);
    }
    cout << ans << " " << mx;
}

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