Submission #378888

#	Time	Username	Problem	Language	Result	Execution time	Memory
378888		2qbingxuan	Nice sequence (IZhO18_sequence)	C++14	100 / 100	480 ms	31304 KiB

sequence

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#endif // local
#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;

        auto ok = [n, m](int L, bool out) {
            vector<int> indeg(L+1);
            for (int i = n; i <= L; i++)
                indeg[i-n] += 1;
            for (int i = m; i <= L; 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;
                if (int j = i-n; j >= 0)
                    if (--indeg[j] == 0)
                        q.push(j);
                if (int j = i+m; j <= L)
                    if (--indeg[j] == 0)
                        q.push(j);
            }
            for (int i = 0; i <= L; i++) if (indeg[i]) return false;
            if (out) {
                cout << L << '\n';
                for (int i = 1; i <= L; i++)
                    cout << vis[i] - vis[i-1] << (i==L ? '\n' : ' ');
            }
            return true;
        };
        /*
        int ans = 0;
        int s = 1;
        while (ok(s, false)) s <<= 1;
        for (; s; s >>= 1)
            if (ok(ans + s, false))
                ans += s;
                */
        debug(n + m - __gcd(n, m) - 1);
        ok(n+m-__gcd(n,m)-1, true);
    }
}

Compilation message (stderr)

sequence.cpp:2: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
    2 | #pragma loop_opt(on)
      | 
sequence.cpp: In lambda function:
sequence.cpp:43:21: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   43 |                 if (int j = i-n; j >= 0)
      |                     ^~~
sequence.cpp:46:21: warning: init-statement in selection statements only available with '-std=c++17' or '-std=gnu++17'
   46 |                 if (int j = i+m; j <= L)
      |                     ^~~

• 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