# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1196721 | m_elgamal | XOR (IZhO12_xor) | C++17 | 1 ms | 320 KiB |
#include "bits/stdc++.h"
#define ll long long
#define el '\n'
using namespace std;
const ll N = 2e5 + 3, mod = 1e9 + 7, inf = 1e18;
map<ll, int> eq;
vector<array<int, 2>> id(64);
class BinaryTrie
{
private:
struct Node
{
Node* ch[2];
int fr;
Node() : fr(0) {
memset(ch, 0, sizeof ch);
}
};
public:
Node* root = new Node();
BinaryTrie() { insert(0); }
void insert(ll x) {
Node* cur = root;
for (int i = 62; i >= 0; i--) {
int bit = (x >> i) & 1;
if (!cur->ch[bit])
cur->ch[bit] = new Node();
cur = cur->ch[bit];
cur->fr++;
}
}
void erase(ll x) {
Node* cur = root;
for (int i = 62; i >= 0; i--) {
int bit = (x >> i) & 1;
cur = cur->ch[bit];
cur->fr--;
}
}
int query(ll y, ll x) {
Node* cur = root;
int mn = 66;
for (int i = 62; i >= 0; i--) {
int xb = (x >> i) & 1, yb = (y >> i) & 1;
if (xb == 0 && cur->ch[!yb])
mn = min(mn, id[i][!yb] + 1);
xb ^= yb;
if (!cur->ch[xb])
return mn;
cur = cur->ch[xb];
}
x ^= y;
return min(mn, eq[x] + 1);
}
};
void solve() {
ll n, x;
cin >> n >> x;
BinaryTrie trie;
ll pre = 0;
int l = -1, k = -1;
for (int i = 1; i <= n; i++) {
ll a;
cin >> a;
pre ^= a;
eq[pre] = (eq.count(pre) ? eq[pre] : i);
for (int j = 0; j < 63; j++)
if ((pre >> j) & 1)
id[j][1] = (!id[j][1] ? i : id[j][1]);
else
id[j][0] = (!id[j][0] ? i : id[j][0]);
int j = trie.query(pre, x);
if (j != 66 && (k == -1 || i - j + 1 > k))
k = i - j + 1, l = j;
trie.insert(pre);
}
cout << l << " " << k << el;
}
/*
*/
signed main() {
ios_base::sync_with_stdio(0);
cout.tie(0), cin.tie(0);
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int _t = 1;
// cin >> _t;
while (_t--) {
solve();
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |