Submission #682583

#	Time	Username	Problem	Language	Result	Execution time	Memory
682583		FedShat	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2074 ms	25968 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int l = 0, r = 2 * (n + m) + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            vector<vector<int>> g(mid + 1); // i -> j means pref[i] > pref[j]
            for (int i = 0; i + m <= mid; ++i) {
                g[i + m].push_back(i);
            }
            for (int i = 0; i + n <= mid; ++i) {
                g[i].push_back(i + n);
            }
            vector<int> used(mid + 1, -1);
            bool cycle = 0;
            auto dfs = [&](auto dfs, int v) -> void {
                used[v] = 0;
                for (auto u : g[v]) {
                    if (used[u] == -1) {
                        dfs(dfs, u);
                    } else if (used[u] == 0) {
                        cycle = 1;
                    }
                }
                used[v] = 1;
            };
            for (int i = 0; i <= mid; ++i) {
                if (used[i] == -1) {
                    dfs(dfs, i);
                }
            }
            if (!cycle) {
                l = mid;
            } else {
                r = mid;
            }
        }
        vector<vector<int>> g(l + 1); // i -> j means pref[i] > pref[j]
        for (int i = 0; i + m <= l; ++i) {
            g[i + m].push_back(i);
        }
        for (int i = 0; i + n <= l; ++i) {
            g[i].push_back(i + n);
        }
        vector<ll> dp(l + 1);
        vector<bool> used(l + 1);
        auto dfs = [&](auto dfs, int v) -> void {
            used[v] = 1;
            for (auto u : g[v]) {
                if (!used[u]) {
                    dfs(dfs, u);
                }
                dp[v] = max(dp[v], dp[u] + 1);
            }
            dp[v] = max(dp[v], v + 1ll);
        };
        for (int i = 0; i <= l; ++i) {
            if (!used[i]) {
                dfs(dfs, i);
            }
        }
        for (int i = 0; i + m <= l; ++i) {
            assert(dp[i + m] > dp[i]);
        }
        for (int i = 0; i + n <= l; ++i) {
            assert(dp[i + n] < dp[i]);
        }
        cout << l << "\n";
        for (int i = 1; i <= l; ++i) {
            assert(dp[i] != dp[i - 1]);
            cout << dp[i] - dp[i - 1] << " ";
        }
        cout << "\n";
    }
}

• 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