結果
問題 |
No.2977 Kth Xor Pair
|
ユーザー |
|
提出日時 | 2025-08-21 07:26:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,861 ms / 3,000 ms |
コード長 | 978 bytes |
コンパイル時間 | 1,025 ms |
コンパイル使用メモリ | 92,176 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2025-08-21 07:27:20 |
合計ジャッジ時間 | 40,910 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <iostream> #include <cmath> #include <map> using namespace std; int a[200010]; int main() { int n; long long k; cin >> n >> k; k--; int maxn = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; maxn = max(maxn, a[i]); } int ans = 0; for (int i = log2(maxn); i >= 0; i--) { map<int, int> m; for (int j = 1; j <= n; j++) { m[(a[j] >> i) << i]++; } long long cnt = 0; for (auto j : m) { int t = j.first ^ ans; if (j.first > t) { continue; } if (!ans) { cnt += ((long long)j.second * (j.second - 1)) >> 1; } else { if (m.count(t)) { cnt += (long long)j.second * m[t]; } } } if (cnt <= k) { ans |= 1 << i; k -= cnt; } } cout << ans; return 0; }