Submission #614755

#	Time	Username	Problem	Language	Result	Execution time	Memory
614755		KoD	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2055 ms	47880 KiB

sequence

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 0 / 24