結果

問題 No.2085 Directed Complete Graph
ユーザー 259_Momone
提出日時 2022-10-08 15:40:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 3,794 bytes
コンパイル時間 3,960 ms
コンパイル使用メモリ 252,496 KB
最終ジャッジ日時 2025-02-08 00:28:24
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0