結果

問題 No.2977 Kth Xor Pair
ユーザー tassei903tassei903
提出日時 2024-12-02 18:25:18
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,546 ms / 3,000 ms
コード長 4,349 bytes
コンパイル時間 3,858 ms
コンパイル使用メモリ 278,496 KB
実行使用メモリ 86,132 KB
最終ジャッジ日時 2024-12-02 18:26:12
合計ジャッジ時間 52,602 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 5 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 1,015 ms
44,756 KB
testcase_08 AC 2,329 ms
85,960 KB
testcase_09 AC 2,090 ms
85,924 KB
testcase_10 AC 2,038 ms
86,064 KB
testcase_11 AC 2,100 ms
86,084 KB
testcase_12 AC 1,985 ms
86,064 KB
testcase_13 AC 2,300 ms
85,988 KB
testcase_14 AC 951 ms
44,600 KB
testcase_15 AC 1,886 ms
86,008 KB
testcase_16 AC 2,311 ms
86,132 KB
testcase_17 AC 2,170 ms
86,004 KB
testcase_18 AC 2,381 ms
86,000 KB
testcase_19 AC 2,431 ms
86,000 KB
testcase_20 AC 2,321 ms
86,132 KB
testcase_21 AC 2,442 ms
86,004 KB
testcase_22 AC 2,528 ms
86,004 KB
testcase_23 AC 2,546 ms
86,004 KB
testcase_24 AC 2,453 ms
86,004 KB
testcase_25 AC 2,351 ms
86,000 KB
testcase_26 AC 2,533 ms
86,004 KB
testcase_27 AC 497 ms
6,776 KB
testcase_28 AC 351 ms
6,648 KB
testcase_29 AC 380 ms
6,776 KB
testcase_30 AC 438 ms
6,640 KB
testcase_31 AC 427 ms
6,644 KB
testcase_32 AC 349 ms
5,248 KB
testcase_33 AC 356 ms
5,248 KB
testcase_34 AC 357 ms
5,248 KB
testcase_35 AC 354 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function 'void binary_trie<LOGMAX, Int>::apply_xor(Int) [with int LOGMAX = 31; Int = unsigned int]',
    inlined from 'void solve()' at main.cpp:161:27:
main.cpp:100:9: warning: 'trie.binary_trie<31, unsigned int>::xor_lazy' may be used uninitialized [-Wmaybe-uninitialized]
  100 |         xor_lazy ^= x;
      |         ^~~~~~~~
main.cpp: In function 'void solve()':
main.cpp:146:31: note: 'trie' declared here
  146 |     binary_trie<31, uint32_t> trie;
      |                               ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep1(n) for(int i = 0; i < (int)n; i++)
#define rep2(i, n) for(int i = 0; i < (int)n; i++)
#define rep3(i, l, r) for(int i = (int)l; i < (int)r; i++)
#define overloadrep(a, b, c, x, ...) x
#define rep(...) overloadrep(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

using ll = long long;
using vi = vector<int>;
using pll = pair<ll, ll>;


template<int LOGMAX, typename Int>
struct binary_trie {

    struct node {
        int p;
        array<int, 2> c;
        int cnt, acc;
    };

    Int xor_lazy;
    vector<node> tree;

    binary_trie() {
        tree.emplace_back(node{-1, {-1, -1}, 0, 0});
    }

    Int kth_element(int k);

    void insert(Int x) {
        int idx = 0;
        x ^= xor_lazy;
        rrep(i, LOGMAX) {
            tree[idx].acc++;
            if (tree[idx].c[x >> i & 1] == -1) {
                tree.emplace_back(node{idx, {-1, -1}, 0, 0});
                tree[idx].c[x >> i & 1] = sz(tree) - 1;
                idx = sz(tree) - 1;
            } 
            else {
                idx = tree[idx].c[x >> i & 1];
            }
        }
        tree[idx].acc++;
        tree[idx].cnt++;
    }

    void erase(Int x) {
        int idx = 0;
        x ^= xor_lazy;
        rrep(i, LOGMAX) {
            tree[idx].acc--;
            if (tree[idx].c[x >> i & 1] == -1) {
                tree.emplace_back(node{idx, {-1, -1}, 0, 0});
                tree[idx].c[x >> i & 1] = sz(tree) - 1;
                idx = sz(tree) - 1;
                
            } 
            else {
                idx = tree[idx].c[x >> i & 1];
            }
        }
        tree[idx].acc--;
        tree[idx].cnt--;
    }

    int find(Int x) {
        int idx = 0;
        x ^= xor_lazy;
        rrep(i, LOGMAX) {
            if (tree[idx].c[x >> i & 1] == -1) {
                return -1;
            } 
            else {
                idx = tree[idx].c[x >> i & 1];
            }
        }
        return idx;
    }

    int count(Int x) {
        int res = find(x);
        if (res == -1) return 0;
        return tree[res].cnt;
    }

    void apply_xor(Int x) {
        xor_lazy ^= x;
    }

    int order(Int x) {
        int idx = 0;
        int res = 0;
        rrep(i, LOGMAX) {
            // cerr << i << " " << idx << endl;
            int rev = xor_lazy >> i & 1;
            if (x >> i & 1) {
                if (tree[idx].c[rev] != -1) res += tree[tree[idx].c[rev]].acc;
                if (tree[idx].c[rev ^ 1] == -1) break;
                idx = tree[idx].c[rev ^ 1];
            }
            else {
                if (tree[idx].c[rev] == -1) break;
                idx = tree[idx].c[rev];
            }
        }
        return res;
    }

    Int min() {
        int idx = 0;
        Int res = 0;
        rrep(i, LOGMAX) {
            int rev = xor_lazy >> i & 1;
            if (tree[idx].c[rev] != -1 && tree[tree[idx].c[rev]].acc > 0) {
                idx = tree[idx].c[rev];
            }
            else {
                idx = tree[idx].c[rev ^ 1];
                res |= (Int)1 << i;
            }
        }
        return res;
    }
};



void solve() {
    
    int n;ll k; cin >> n >> k;
    k = (ll)n * (n - 1) / 2 - k +1;
    vector<uint32_t> a(n);rep(i, n) cin >> a[i];
    binary_trie<31, uint32_t> trie;

    rep(i, n) {
        trie.insert(a[i]);
    }

    // rep(i, 100) {
    //     cout << trie.order(i) << endl;
    // }

    int ok = 0, ng = 1<<30;
    while (abs(ok - ng) > 1) {
        int mid = ng + (ok - ng) / 2;
        ll res = 0;
        rep(i, n){
            trie.apply_xor(a[i]);
            res += n - trie.order(mid);
            trie.apply_xor(a[i]);
        }
        if (mid == 0) res -= n;
        res /= 2;
        // cerr << mid << " " << res << endl;
        if (res >= k) {
            ok = mid;
        }
        else {
            ng = mid;
        }
    } 
    cout << ok << endl;

}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // int T;cin >> T;
    while(T--) {
        solve();
    }
    
}
0