제출 #1166593

#제출 시각아이디문제언어결과실행 시간메모리
1166593ezzatw122XOR (IZhO12_xor)C++20
0 / 100
75 ms35336 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 = 2e5 + 5; struct trie { struct node { int nxt[2]; vector<int> idx; node() { nxt[0] = nxt[1] = -1; } }; vector<node> tr; int sz; trie() { tr.push_back(node()); sz = 0; } void update(int x, int idx) { int cur = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; if (!~tr[cur].nxt[bit]) { tr.push_back(node()); tr[cur].nxt[bit] = ++sz; } cur = tr[cur].nxt[bit]; } tr[cur].idx.push_back(idx); } int query(int x, int k, int idx, bool ok = 0, int curr = 0) { int bitx = (x >> idx) & 1; int bitk = (k >> idx) & 1; int ret = 3e5; if (ok) { for (auto j: tr[curr].idx) { ret = min(ret, j); } } if (idx == -1) return ret; if (~tr[curr].nxt[0] && ((bitk && bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[0])); if (~tr[curr].nxt[0] && ((!bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[0])); if (~tr[curr].nxt[0] && ((!bitk && bitx) or ok))ret = min(ret, query(x, k, idx - 1, 1, tr[curr].nxt[0])); if (~tr[curr].nxt[1] && ((bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 0, tr[curr].nxt[1])); if (~tr[curr].nxt[1] && ((!bitk && !bitx) or ok))ret = min(ret, query(x, k, idx - 1, 1, tr[curr].nxt[1])); return ret; } }; void code() { int n, x; cin >> n >> x; vector<int> v(n + 1); for (int i = 1; i <= n; i++) { cin >> v[i]; v[i] = v[i - 1] ^ v[i]; } trie tr; tr.update(0, 0); int mx = 0, idx = -1; for (int i = 1; i <= n; i++) { int len = i - tr.query(v[i], x - 1, 30); if (len > mx) { mx = len; idx = i; } tr.update(v[i], i); } cout << idx - mx + 1 << " " << mx << "\n"; } int main() { read(); int t = 1; // cin >> t; while (t--) code(); }
#Verdict Execution timeMemoryGrader output
Fetching results...