結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー Gandalfr
提出日時 2024-03-28 02:13:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,406 ms / 3,000 ms
コード長 6,167 bytes
コンパイル時間 4,257 ms
コンパイル使用メモリ 322,276 KB
実行使用メモリ 454,656 KB
最終ジャッジ日時 2024-09-30 14:40:56
合計ジャッジ時間 22,453 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "src/main.cpp"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#line 2 "library/gandalfr/types.hpp"

#line 5 "library/gandalfr/types.hpp"

namespace gandalfr {

using i8 = __int8_t;
using i16 = __int16_t;
using i32 = __int32_t;
using i64 = __int64_t;
using i128 = __int128_t;

using u8 = __uint8_t;
using u16 = __uint16_t;
using u32 = __uint32_t;
using u64 = __uint64_t;
using u128 = __uint128_t;

constexpr i8 IMAX8 = INT8_MAX;
constexpr i16 IMAX16 = INT16_MAX;
constexpr i32 IMAX32 = INT32_MAX;
constexpr i64 IMAX64 = INT64_MAX;

constexpr i8 IMIN8 = INT8_MIN;
constexpr i16 IMIN16 = INT16_MIN;
constexpr i32 IMIN32 = INT32_MIN;
constexpr i64 IMIN64 = INT64_MIN;

constexpr u8 UMAX8 = UINT8_MAX;
constexpr u16 UMAX16 = UINT16_MAX;
constexpr u32 UMAX32 = UINT32_MAX;
constexpr u64 UMAX64 = UINT64_MAX;

constexpr i64 MOD998 = 998244353;
constexpr i64 MOD107 = 1000000007;

constexpr double PI = M_PI;

const i32 INF = 1001001001;
const i64 INFLL = 1001001001001001001;
#define rep(i, j, n) for (i64 i = (i64)(j); i < (i64)(n); i++)
#define rrep(i, j, n) for (i64 i = (i64)(n - 1); i >= (i64)(j); i--)
#define all(a) (a).begin(), (a).end()
#define LF cout << endl
template <typename T> void print_debug(T t) { std::cerr << t << std::endl; }
template <typename First, typename... Rest>
void print_debug(First parm1, Rest... parm) {
    std::cerr << parm1 << ", ", print_debug(parm...);
}
#define debug(...)                                                             \
    {                                                                          \
        std::cerr << #__VA_ARGS__ << ": ";                                     \
        print_debug(__VA_ARGS__);                                              \
    }
template <typename T> inline bool chmax(T &a, const T &b) {
    return a < b && (a = b, true);
}
template <typename T> inline bool chmin(T &a, const T &b) {
    return a > b && (a = b, true);
}
template <typename Key, typename Value>
inline bool map_chmax(std::map<Key, Value> &mp, const Key &a, const Value &b) {
    auto it = mp.find(a);
    return it == mp.end() ? (mp[a] = b, true) : chmax(it->second, b);
}
template <typename Key, typename Value>
inline bool map_chmin(std::map<Key, Value> &mp, const Key &a, const Value &b) {
    auto it = mp.find(a);
    return it == mp.end() ? (mp[a] = b, true) : chmin(it->second, b);
}
void Yes(bool ok) { std::cout << (ok ? "Yes" : "No") << std::endl; }

} // namespace gandalfr
#line 2 "library/gandalfr/data_structure/BinaryTrie.hpp"

#line 6 "library/gandalfr/data_structure/BinaryTrie.hpp"

namespace gandalfr {

template <u32 bit_width> struct BinaryTrie {
    static_assert(bit_width <= 64, "bit_width must be 64 or less");

  private:
    struct BinaryTrieNode {
        std::shared_ptr<BinaryTrieNode> children[2] = {nullptr, nullptr};
        u32 level, sub_cnt = 0;
        BinaryTrieNode(u32 lvl) : level(lvl) {}
        // 00: xx, 01: xo, 10: ox, 11: oo
        u32 stateOfChildren() const {
            return ((bool)children[1] << 1) | (bool)children[0];
        }
        bool isLeaf() const {
            return level == 0;
        }
        bool nextIndex(u64 n) const {
            return (n >> (level - 1)) & 1;
        }
    };
    using NodePtr = std::shared_ptr<BinaryTrieNode>;
    NodePtr root = std::make_shared<BinaryTrieNode>(bit_width);

    NodePtr getNodePtr(u64 n) const {
        NodePtr cur = root;
        while (!cur->isLeaf()) {
            bool b = cur->nextIndex(n);
            if (!cur->children[b]) {
                return nullptr;
            }
            cur = cur->children[b];
        }
        return cur;
    }

  public:
    void insert(u64 n) {
        NodePtr cur = root;
        while (cur->level) {
            cur->sub_cnt += 1;
            bool b = cur->nextIndex(n);
            if (!cur->children[b]) {
                cur->children[b] =
                    std::make_shared<BinaryTrieNode>(cur->level - 1);
            }
            cur = cur->children[b];
        }
        cur->sub_cnt += 1;
    }

    u32 size() const {
        return root->sub_cnt;
    }

    u32 count(u64 n) const {
        NodePtr ptr = getNodePtr(n);
        return (ptr ? ptr->sub_cnt : 0);
    }

    void erase(u64 n) const {
        u32 cnt = count(n);
        if (cnt == 0) return;
        NodePtr cur = root;
        while (true) {
            cur->sub_cnt -= cnt;
            bool b = cur->nextIndex(n);
            if (cur->children[b]->sub_cnt == cnt) {
                cur->children[b] = nullptr;
                return;
            }
            cur = cur->children[b];
        }
    }

    void eraseOne(u64 n) const {
        if (count(n) == 0) return;
        NodePtr cur = root;
        while (!cur->isLeaf()) {
            cur->sub_cnt -= 1;
            bool b = cur->nextIndex(n);
            if (cur->children[b]->sub_cnt == 1) {
                cur->children[b] = nullptr;
                return;
            }
            cur = cur->children[b];
        }
        cur->sub_cnt -= 1;
    }

    u64 nthElement(u32 n) const {
        assert(n < size());
        u64 ret = 0;
        NodePtr cur = root;
        while (!cur->isLeaf()) {
            ret <<= 1;
            u32 state = cur->stateOfChildren();
            assert(state > 0);
            if (state == 1 || (state == 3 && n < cur->children[0]->sub_cnt)) {
                cur = cur->children[0];
            } else {
                n -= (state & 1 ? cur->children[0]->sub_cnt : 0);
                cur = cur->children[1];
                ret |= 1;
            }
        }
        return ret;
    }

};
} // namespace gandalfr
#line 5 "src/main.cpp"
using namespace std;
using namespace gandalfr;

int main(void) {

    i32 Q, K;
    cin >> Q >> K;
    BinaryTrie<64> bt;
    rep(i,0,Q) {
        i32 q;
        cin >> q;
        if (q == 1) {
            u64 x;
            cin >> x;
            bt.insert(x);
        } else {
            if (bt.size() < K) {
                cout << -1 << endl;
            } else {
                i64 n = bt.nthElement(K - 1);
                bt.eraseOne(n);
                cout << n << "\n";                
            }

        }
    }

}
0