제출 #1196721

#제출 시각아이디문제언어결과실행 시간메모리
1196721m_elgamalXOR (IZhO12_xor)C++17
0 / 100
1 ms320 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) 메시지

xor.cpp: In function 'int main()':
xor.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...