제출 #614755

#제출 시각아이디문제언어결과실행 시간메모리
614755KoDNice sequence (IZhO18_sequence)C++17
76 / 100
2055 ms47880 KiB
#include <bits/stdc++.h>

using std::vector;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

vector<int> solve(const int N, const int M) {
    vector<int> ret;
    const auto gen = [&](const int len) {
        vector<int> state(len + 1), order;
        order.reserve(len + 1);
        const auto dfs = fixed([&](auto&& dfs, const int u) -> bool {
            if (state[u] == 1) return true;
            if (state[u] == -1) return false;
            state[u] = -1;
            if (u >= M and !dfs(u - M)) return false;
            if (u + N <= len and !dfs(u + N)) return false;
            order.push_back(u);
            state[u] = 1;
            return true;
        });
        for (int i = 0; i <= len; ++i) {
            if (!dfs(i)) return false;
        }
        vector<int> rank(len + 1);
        for (int i = 0; i <= len; ++i) {
            rank[order[i]] = i;
        }
        ret.resize(len);
        for (int i = 0; i < len; ++i) {
            ret[i] = rank[i + 1] - rank[i];
        }
        return true;
    };
    int ok = 0, ng = N + M;
    while (ng - ok > 1) {
        const int md = (ok + ng) / 2;
        (gen(md) ? ok : ng) = md;   
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) {
        int N, M;
        std::cin >> N >> M;
        const auto A = solve(N, M);
        std::cout << A.size() << '\n';
        for (int i = 0; i < (int)A.size(); ++i) {
            if (i > 0) std::cout << ' ';
            std::cout << A[i];
        }
        std::cout << '\n';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...