Submission #485548

#	Time	Username	Problem	Language	Result	Execution time	Memory
485548		SirCovidThe19th	Nice sequence (IZhO18_sequence)	C++17	100 / 100	421 ms	34804 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

int main(){
    int tc; cin >> tc;
    while (tc--){
        int n, m, sz; cin >> n >> m; sz = n + m - __gcd(n, m) - 1;

        int indeg[sz + 1] = {}, pre[sz + 1], cnt = 0; queue<int> q; vector<int> ord; 

        for (int i = 0; i <= sz; i++){
            if (i + m <= sz) indeg[i + m]++;
            if (i - n >= 0) indeg[i - n]++;
        }
        for (int i = 0; i <= sz; i++) if (!indeg[i]) q.push(i);

        while (!q.empty()){
            int cur = q.front(); ord.push_back(cur); q.pop();
            if (cur + m <= sz){
                indeg[cur + m]--;
                if (!indeg[cur + m]) q.push(cur + m);
            }
            if (cur - n >= 0){
                indeg[cur - n]--;
                if (!indeg[cur - n]) q.push(cur - n);
            }
        }
        for (int x : ord) pre[x] = ++cnt;

        cout<<sz<<endl;
        for (int i = 1; i <= sz; i++) cout<<pre[i] - pre[i - 1]<<" ";
        cout<<endl;
    }
}

• 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