結果

問題 No.2085 Directed Complete Graph
ユーザー 259_Momone259_Momone
提出日時 2022-09-27 03:55:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 3,021 bytes
コンパイル時間 3,076 ms
コンパイル使用メモリ 266,540 KB
実行使用メモリ 25,452 KB
平均クエリ数 2531.18
最終ジャッジ日時 2024-06-02 00:44:44
合計ジャッジ時間 6,744 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 22 ms
24,836 KB
testcase_01 AC 20 ms
24,964 KB
testcase_02 AC 139 ms
25,196 KB
testcase_03 AC 131 ms
24,556 KB
testcase_04 AC 151 ms
24,940 KB
testcase_05 AC 80 ms
24,556 KB
testcase_06 AC 81 ms
24,812 KB
testcase_07 AC 144 ms
24,556 KB
testcase_08 AC 109 ms
24,556 KB
testcase_09 AC 142 ms
24,812 KB
testcase_10 AC 146 ms
25,196 KB
testcase_11 AC 146 ms
25,452 KB
testcase_12 AC 146 ms
24,940 KB
testcase_13 AC 142 ms
24,556 KB
testcase_14 AC 145 ms
24,556 KB
testcase_15 AC 20 ms
24,580 KB
testcase_16 AC 19 ms
24,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>

int main() {
    using namespace std;
    unsigned long N;
    cin >> N;
    auto cmp{[](auto i, auto j) mutable -> bool {
        cout << "? " << i << " " << j << endl;
        unsigned long t;
        cin >> t;
        return t;
    }};
    // from "Improved Average Complexity for Comparison-Based Sorting"
    // Kazuo Iwama, Junichi Teruyama (2017)
    const auto one_two_insertion{[fill{[](unsigned long i){
        i |= i >> 1;
        i |= i >> 2;
        i |= i >> 4;
        i |= i >> 8;
        i |= i >> 16;
        i |= i >> 32;
        return i;
    }}](auto&& seq, auto&& cmp = std::less<>{}){
        const auto binary_search_insert{[&fill, &seq](unsigned long L, unsigned long R, unsigned long idx, auto&& cmp){
            const auto V{seq[idx]};
            rotate(begin(seq) + R, begin(seq) + idx, begin(seq) + idx + 1);
            idx = R++;
            while(L + 1 < R){
                unsigned long x{R - L - 1};
                unsigned long y{fill(x) + 1};
                unsigned long z{3 * y / 4};
                unsigned long M{L + (x < z ? y / 4 : x - y / 2 + 1)};
                (cmp(seq[M - 1], V) ? L : R) = M;
            }
            rotate(begin(seq) + L, begin(seq) + idx, begin(seq) + idx + 1);
            return L;
        }};
        const auto two_merge{[&seq, &binary_search_insert, alpha{[&fill](unsigned long x, unsigned long r){
            if(~r & 1)return x - (x >> (r / 2));
            const auto y{fill(x) + 1};
            if(3 * y < 4 * x)return x - (x >> (r / 2)) + (y >> (r / 2 + 2));
            return x - (x >> (r / 2 + 1)) - (y >> (r / 2 + 3));
        }}](unsigned long L, unsigned long R, unsigned long idx_0, unsigned long idx_1, auto&& cmp){
            if(cmp(seq[idx_1], seq[idx_0]))swap(idx_0, idx_1);
            const auto V{seq[idx_0]};
            unsigned long x{R - L};
            unsigned long l{~0UL}, r{alpha(x, 1)};
            unsigned long now{1};
            while(cmp(seq[L + r], V)){
                l = r;
                r = alpha(x, ++now);
            }
            unsigned long K{binary_search_insert(L + l + 1, L + r, idx_0, cmp)};
            if(idx_0 > idx_1)++idx_1;
            binary_search_insert(K, R + 1, idx_1, cmp);
        }};
        const auto N{size(seq)};
        if(N == 1)return;
        if(cmp(seq[1], seq[0]))swap(seq[0], seq[1]);
        if(N == 2)return;
        for(unsigned long i{2}; i + 1 < N; i += 2){
            if(2093258 * i >= 1142659 * (fill(i) + 1) && 4628523 * i >= 4139462 * (fill(i) + 1))two_merge(0, i, i, i + 1, cmp);
            else{
                binary_search_insert(0, i, i, cmp);
                binary_search_insert(0, i + 1, i + 1, cmp);
            }
        }
        if(N & 1)binary_search_insert(0, N - 1, N - 1, cmp);
    }};
    vector<unsigned long> A(N);
    iota(begin(A), end(A), 1);
    one_two_insertion(A, cmp);
    cout << "!" << endl;
    cout << N - 1 << endl;
    for(const auto a : A)cout << a << " ";
    cout << endl;
    return 0;
}
0