Submission #682609

#	Time	Username	Problem	Language	Result	Execution time	Memory
682609		FedShat	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1119 ms	61292 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;
}

constexpr int N = 4e5 + 1;
int used[N];
bool cycle = 0;
int n, m;

void dfs1(int v, int sz) {
    used[v] = 0;
    for (auto u : {v - m, v + n}) {
        if (u < 0 || u >= sz) {
            continue;
        }
        if (used[u] == -1) {
            dfs1(u, sz);
        } else if (used[u] == 0) {
            cycle = 1;
        }
    }
    used[v] = 1;
}

vector<ll> dp;

void dfs2(int v, int sz) {
    for (auto u : {v - m, v + n}) {
        if (u < 0 || u >= sz) {
            continue;
        }
        if (dp[u] == 0) {
            dfs2(u, sz);
        }
        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--) {
        cin >> n >> m;
        int l = 0, r = n + m;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            cycle = 0;
            memset(used, -1, sizeof(int) * (mid + 1));
            for (int i = 0; i <= mid; ++i) {
                if (used[i] == -1) {
                    dfs1(i, mid + 1);
                }
            }
            if (!cycle) {
                l = mid;
            } else {
                r = mid;
            }
        }
        memset(used, -1, sizeof(int) * (l + 1));
        dp.assign(l + 1, 0);
        for (int i = 0; i <= l; ++i) {
            if (dp[i] == 0) {
                dfs2(i, l + 1);
            }
        }
        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: 24 / 24