Submission #1172090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172090		ivaziva	Nice sequence (IZhO18_sequence)	C++20	100 / 100	967 ms	77172 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define MAXN 400001

int n,m;
vector<int> adj[MAXN];
vector<int> topo;
int indeks[MAXN];bool pos[MAXN];

void dfs(int node)
{
    pos[node]=true;
    for (int sled:adj[node])
    {
        if (!pos[sled]) dfs(sled);
    }
    topo.push_back(node);
}

void init(int len)
{
    for (int i=0;i<=len;i++) {adj[i].clear();pos[i]=false;indeks[i]=0;}
    topo.clear();
}

int main()
{
    int t;cin>>t;
    for (int z=0;z<t;z++)
    {
        cin>>n>>m;int len=n+m-__gcd(n,m)-1;init(len);
        if (n==1 and m==1) {cout<<0<<endl;continue;}
        if (len<=0) {cout<<0<<endl;continue;}
        for (int i=m;i<=len;i++) adj[i-m].push_back(i);
        for (int i=n;i<=len;i++) adj[i].push_back(i-n);
        for (int i=0;i<=len;i++)
        {
            if (!pos[i]) dfs(i);
        }
        reverse(topo.begin(),topo.end());
        for (int i=0;i<topo.size();i++) indeks[topo[i]]=i;
        cout<<len<<endl;
        for (int i=1;i<=len;i++) cout<<indeks[i]-indeks[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