Submission #378878

#	Time	Username	Problem	Language	Result	Execution time	Memory
378878		2qbingxuan	Nice sequence (IZhO18_sequence)	C++14	61 / 100	2029 ms	21084 KiB

sequence

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#define pb emplace_back
#define all(v) begin(v),end(v)

using namespace std;
typedef int64_t ll;

constexpr ll maxn = 300025, INF = 1e18, MOD = 998244353, K = 14699, inf = 1e9;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> jizz;
        auto ok = [n, m, &jizz](int L) {
            vector<vector<int>> g(L+1);
            vector<int> indeg(L+1);
            for (int i = n; i <= L; i++)
                g[i].push_back(i-n), indeg[i-n] += 1;
            for (int i = m; i <= L; i++)
                g[i-m].push_back(i), indeg[i] += 1;
            queue<int> q;
            for (int i = 0; i <= L; i++) if (indeg[i] == 0) q.push(i);
            vector<int> vis(L+1);
            int cur = 0;
            while (!q.empty()) {
                int i = q.front(); q.pop();
                vis[i] = ++cur;
                for (int j: g[i]) if (--indeg[j] == 0) q.push(j);
            }
            for (int i = 0; i <= L; i++) if (indeg[i]) return false;
            jizz = vis;
            return true;
        };
        int ans = 0;
        int s = 1;
        while (ok(s)) s <<= 1;
        for (; s; s >>= 1)
            if (ok(ans + s))
                ans += s;
        ok(ans);
        cout << ans << '\n';
        for (int i = 1; i <= ans; i++)
            cout << jizz[i] - jizz[i-1] << (i==ans ? '\n' : ' ');
    }
}

Compilation message (stderr)

sequence.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      |

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