結果

問題 No.2085 Directed Complete Graph
ユーザー 259_Momone259_Momone
提出日時 2022-10-08 15:40:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 3,794 bytes
コンパイル時間 4,061 ms
コンパイル使用メモリ 262,104 KB
実行使用メモリ 24,420 KB
平均クエリ数 2536.65
最終ジャッジ日時 2023-09-04 21:17:48
合計ジャッジ時間 8,850 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
23,532 KB
testcase_01 AC 25 ms
23,412 KB
testcase_02 AC 156 ms
23,544 KB
testcase_03 AC 148 ms
24,036 KB
testcase_04 AC 165 ms
23,412 KB
testcase_05 AC 91 ms
23,412 KB
testcase_06 AC 94 ms
24,324 KB
testcase_07 AC 161 ms
23,652 KB
testcase_08 AC 123 ms
24,072 KB
testcase_09 AC 158 ms
24,036 KB
testcase_10 AC 164 ms
23,388 KB
testcase_11 AC 167 ms
23,652 KB
testcase_12 AC 165 ms
23,556 KB
testcase_13 AC 165 ms
23,832 KB
testcase_14 AC 165 ms
24,420 KB
testcase_15 AC 26 ms
23,664 KB
testcase_16 AC 26 ms
23,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/extc++.h>

namespace pokalib{
    template<typename T>
    T fill(T x){
        --x;
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        x |= x >> 32;
        return ++x;
    }

    template<typename RandomAccessIterator, typename Comp = std::less<>>
    [[maybe_unused]] std::vector<unsigned long> merge_insertion_sort(RandomAccessIterator first, RandomAccessIterator last, Comp cmp){

        const auto N{last - first};

        std::vector<unsigned long> ret(N);
        std::iota(std::begin(ret), std::end(ret), 0UL);

        if(N == 1)return ret;

        for(unsigned long i{}, j((N + 1) / 2); j < N; ++i, ++j)if(!cmp(first[i], first[j])){
            std::swap(first[i], first[j]);
            std::swap(ret[i], ret[j]);
        }

        if(N == 2)return ret;

        {
            auto permutation{merge_insertion_sort(first + (N + 1) / 2, last, cmp)};

            std::vector<unsigned long> inv(N / 2);
            std::iota(std::begin(inv), std::end(inv), 0UL);
            std::vector<unsigned long> p(N / 2);
            std::iota(std::begin(p), std::end(p), 0UL);

            for(unsigned long i{}; i < N / 2; ++i){
                const auto j{inv[permutation[i]]};
                if(i != j){
                    std::swap(first[i], first[j]);
                    std::swap(ret[i], ret[j]);
                    std::swap(ret[i + (N + 1) / 2], ret[j + (N + 1) / 2]);
                    std::swap(p[i], p[j]);
                    std::swap(inv[p[i]], inv[p[j]]);
                }
            }
        }

        std::vector<unsigned long> inv(N + 1);
        std::iota(std::begin(inv), std::end(inv), 0UL);
        std::vector<unsigned long> p(N + 1);
        std::iota(std::begin(p), std::end(p), 0UL);

        const auto swap{[&first, &ret, &inv, &p](unsigned long x, unsigned long y){
            if(x == y)return;
            std::swap(first[x], first[y]);
            std::swap(ret[x], ret[y]);
            std::swap(p[x], p[y]);
            std::swap(inv[p[x]], inv[p[y]]);
        }};
        const auto rotate{[&swap](unsigned long L, unsigned long R){
            for(unsigned long i{R}; --i > L; )swap(L, i);
        }};
        const auto right_heavy_binary_search{[&first, &cmp, &rotate](unsigned long X, unsigned long L, unsigned long R){
            while(L + 1 < R){
                unsigned long x{R - L};
                unsigned long y{fill(x)};
                unsigned long z{3 * y / 4};
                unsigned long M{L + (x < z ? y / 4 : x - y / 2)};
                (cmp(first[M], first[X]) ? L : R) = M;
            }
            rotate(X, R);
        }};
        rotate(0, (N + 1) / 2);
        unsigned long L{1}, R{std::min<unsigned long>(3, (N + 1) / 2)}, C{8}, now{1};
        while(L < (N + 1) / 2){
            for(unsigned long i{R}; i-- > L; ++now)right_heavy_binary_search(i - L, (N + 1) / 2 - now - 1, inv[i + (N + 1) / 2]);
            C *= 2;
            L = R;
            R = std::min<decltype(R)>((C + 1) / 3, (N + 1) / 2);
        }

        return ret;
    }

    template<typename RandomAccessIterator, typename Comp = std::less<>>
    void sort_less_compare(RandomAccessIterator first, RandomAccessIterator last, Comp cmp){
        merge_insertion_sort(first, last, cmp);
    }
}

int main() {
    using namespace std;
    unsigned long N;
    cin >> N;
    const auto cmp{[](auto i, auto j) -> bool {
        cout << "? " << i << " " << j << endl;
        unsigned long T;
        cin >> T;
        return T;
    }};
    vector<unsigned long> A(N);
    iota(begin(A), end(A), 1);
    pokalib::sort_less_compare(begin(A), end(A), cmp);
    cout << "!\n" << N - 1 << endl;
    for(const auto a : A)cout << a << " ";
    cout << endl;
    return 0;
}
0