제출 #682591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682591		FedShat	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2071 ms	43808 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;
}

vector<vector<int>> g; // i -> j means pref[i] > pref[j]
vector<int> used;
bool cycle = 0;

void dfs1(int v) {
    used[v] = 0;
    for (auto u : g[v]) {
        if (used[u] == -1) {
            dfs1(u);
        } else if (used[u] == 0) {
            cycle = 1;
        }
    }
    used[v] = 1;
}

vector<ll> dp;

void dfs2(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs2(u);
        }
        dp[v] = max(dp[v], dp[u] + 1);
    }
    dp[v] = max(dp[v], v + 1ll);
}

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 = n + m;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            g.clear();
            g.resize(mid + 1);
            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);
            }
            cycle = 0;
            used.assign(mid + 1, -1);
            for (int i = 0; i <= mid; ++i) {
                if (used[i] == -1) {
                    dfs1(i);
                }
            }
            if (!cycle) {
                l = mid;
            } else {
                r = mid;
            }
        }
        g.clear();
        g.resize(l + 1);
        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);
        }
        used.assign(l + 1, 0);
        dp.assign(l + 1, 0);
        for (int i = 0; i <= l; ++i) {
            if (!used[i]) {
                dfs2(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