Submission #1172090

#TimeUsernameProblemLanguageResultExecution timeMemory
1172090ivazivaNice sequence (IZhO18_sequence)C++20
100 / 100
967 ms77172 KiB
#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;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...