結果

問題 No.2977 Kth Xor Pair
ユーザー tassei903
提出日時 2024-12-02 18:25:18
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
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