結果

問題 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  
実行時間 162 ms / 2,000 ms
コード長 3,021 bytes
コンパイル時間 2,805 ms
コンパイル使用メモリ 262,240 KB
実行使用メモリ 24,384 KB
平均クエリ数 2531.18
最終ジャッジ日時 2023-08-24 03:30:52
合計ジャッジ時間 6,302 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
24,360 KB
testcase_01 AC 25 ms
23,664 KB
testcase_02 AC 150 ms
24,384 KB
testcase_03 AC 143 ms
23,580 KB
testcase_04 AC 162 ms
24,108 KB
testcase_05 AC 84 ms
24,024 KB
testcase_06 AC 90 ms
23,244 KB
testcase_07 AC 155 ms
24,084 KB
testcase_08 AC 121 ms
24,036 KB
testcase_09 AC 150 ms
24,312 KB
testcase_10 AC 158 ms
24,024 KB
testcase_11 AC 157 ms
24,312 KB
testcase_12 AC 158 ms
24,084 KB
testcase_13 AC 157 ms
23,604 KB
testcase_14 AC 155 ms
24,348 KB
testcase_15 AC 22 ms
23,460 KB
testcase_16 AC 22 ms
23,592 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