Submission #1166617

#TimeUsernameProblemLanguageResultExecution timeMemory
1166617ezzatw122XOR (IZhO12_xor)C++20
100 / 100
84 ms24980 KiB
#include <bits/stdc++.h> // you just try again using namespace std; #define ll long long void read() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); } const int N = 3e5 + 5; struct trie { vector<array<int, 3> > tree; // 0 , 1 , minidx; int len; trie() { len = 0; tree.push_back({-1, -1, N}); } void insert(int val, int id) { int idx = 0; for (int i = 30; ~i; i--) { int bit = (val >> i) & 1; if (tree[idx][bit] == -1) { tree.push_back({-1, -1, N}); tree[idx][bit] = ++len; } idx = tree[idx][bit]; tree[idx][2] = min(tree[idx][2], id); } } int query(int x, int k) { int idx = 0, ret = N; for (int i = 30; ~i; --i) { int bitx = (x >> i) & 1; int bitk = (k >> i) & 1; if (!bitk && ~tree[idx][bitx ^ 1])ret = min(ret, tree[tree[idx][bitx ^ 1]][2]); if (tree[idx][bitk ^ bitx] == -1)break; idx = tree[idx][bitk ^ bitx]; } return ret; } }; void code() { int n, k; cin >> n >> k; trie tr; tr.insert(0, 0); int idx, mx = 0, pre = 0; for (int i = 1; i <= n; i++) { int val; cin >> val; pre ^= val; int len = i - tr.query(pre, k - 1); if (len > mx) { mx = len; idx = i; } tr.insert(pre,i); } cout << idx - mx + 1 << " " << mx; } int main() { read(); int t = 1; // cin >> t; while (t--) code(); }
#Verdict Execution timeMemoryGrader output
Fetching results...