Submission #485538

#	Time	Username	Problem	Language	Result	Execution time	Memory
485538		SirCovidThe19th	Nice sequence (IZhO18_sequence)	C++17	100 / 100	384 ms	40236 KiB

sequence

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

int n, m, ti = 0, sz, pre[1000005], vis[1000005];

void dfs(int cur){
    if (vis[cur]) return;
    vis[cur] = ++ti;
    if (cur - n >= 0) pre[cur - n] = pre[cur] + 1, dfs(cur - n); 
    if (cur + m <= sz) pre[cur + m] = pre[cur] + 1, dfs(cur + m);
}

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

        for (int i = 0; i <= sz; i++) if (!vis[i]) pre[i] = -(++ti), dfs(i);

        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