#1029780 (C++23) No.2977 Kth Xor Pair

• 問題: No.2977 Kth Xor Pair
• ユーザー: isee
• 提出日時: 2024-12-03 19:52:53
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,220 ms / 3,000 ms
• コード長: 2,481 bytes
• コンパイル時間: 1,859 ms
• コンパイル使用メモリ: 131,612 KB
• 実行使用メモリ: 83,084 KB
• 最終ジャッジ日時: 2024-12-03 19:53:11
• 合計ジャッジ時間: 16,849 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 34

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// https://yukicoder.me/submissions/1029779
#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;
// Function to count 0s and 1s in bit position `i`
pair<long long, long long> count01(const vector<long long>& L, long long i) {
    long long czero = 0, cone = 0;
    for (long long a : L) {
        if ((a >> i) & 1) {
            cone++;
        } else {
            czero++;
        }
    }
    return {czero, cone};
}
// Function to divide the list into 0-group and 1-group based on bit position `i`
pair<vector<long long>, vector<long long>> div01(const vector<long long>& L, long long i) {
    vector<long long> rzero, rone;
    for (long long a : L) {
        if ((a >> i) & 1) {
            rone.push_back(a);
        } else {
            rzero.push_back(a);
        }
    }
    return {rzero, rone};
}
signed main() {
    // Input
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (long long i = 0; i < N; ++i) {
        cin >> A[i];
    }
    // Calculation & Output
    K--;
    K *= 2;
    K += N;
    vector<pair<vector<long long>, vector<long long>>> pairs = {{A, A}};
    long long ans = 0;
    for (long long i = 29; i >= 0; --i) {
        ans <<= 1;
        long long czero = 0;
        for (auto& p : pairs) {
            auto [lz, lo] = count01(p.first, i);
            auto [rz, ro] = count01(p.second, i);
            czero += lz * rz + lo * ro;
        }
        vector<pair<vector<long long>, vector<long long>>> npairs;
        if (K >= czero) {
            ans += 1;
            K -= czero;
            for (auto& p : pairs) {
                auto [lz, lo] = div01(p.first, i);
                auto [rz, ro] = div01(p.second, i);
                if (!lz.empty() && !ro.empty()) {
                    npairs.push_back({lz, ro});
                }
                if (!lo.empty() && !rz.empty()) {
                    npairs.push_back({lo, rz});
                }
            }
        } else {
            for (auto& p : pairs) {
                auto [lz, lo] = div01(p.first, i);
                auto [rz, ro] = div01(p.second, i);
                if (!lz.empty() && !rz.empty()) {
                    npairs.push_back({lz, rz});
                }
                if (!lo.empty() && !ro.empty()) {
                    npairs.push_back({lo, ro});
                }
            }
        }
        pairs = npairs;
    }
    cout << ans << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX