Submission #635005

#TimeUsernameProblemLanguageResultExecution timeMemory
635005drkarlicio2107Nice sequence (IZhO18_sequence)C++14
100 / 100
1998 ms84636 KiB
#include <bits/stdc++.h> using namespace std; int vis [400010]; long long int c=0; long long int n, m; vector < int > g [400010]; vector < long long int > ans; long long int o [400010]; int vis2 [400010]; int vis3 [400010]; void dfs ( int x, long long int d){ if (vis [x]) return ; vis [x]=1; if (x+n<=d){ g [x+n].push_back (x); //dfs (x+n, d); } if (x+m<=d){ g [x].push_back (x+m); dfs (x+m, d); } return ; } void dfs2 ( int v) { vis2[v]=1; for ( long long int u : g[v]) { if (!vis2[u]) dfs2(u); } ans.push_back(v); return ; } void is_cycle ( long long int x) { if (vis3 [x]==1){ c=1; return ; } if (vis3 [x]) return ; vis3 [x]=1; for ( long long int u : g[x]) is_cycle (u); vis3 [x]=2; return ; } void sort_top( long long int d) { memset (vis2, 0, sizeof vis2); ans.clear(); for ( long long int i=0; i<=d; i++) { if (!vis2[i]) dfs2(i); } reverse(ans.begin(), ans.end()); return ; } long long int ok ( long long int d){ memset (vis, 0, sizeof vis); memset (vis3, 0, sizeof vis3); c=0; for ( long long int i=0; i<400010; i++) g [i].clear(); for ( long long int i=0; i<=d; i++){ if (!vis [i]) dfs (i, d); } for ( long long int i=1; i<=d; i++) is_cycle (i); if (c) return 0; sort_top (d); return 1; } int main(){ long long int t; cin >> t; while (t--){ ans.clear (); cin >> n >> m; ok (n+m-__gcd(n,m)-1); int lo=n+m-__gcd(n,m)-1; cout << lo << endl; if (lo==0) continue; long long int pr=0; for ( long long int i=0; i<=lo; i++){ if (ans [lo]==0) break; pr--; } for ( long long int i=0; i<=lo; i++){ //cout << ans [i] << " "; o [ans [i]]=pr; pr++; } for ( long long int i=1; i<lo+1; i++){ //cout << o [i] << "x"; cout << o [i]-o [i-1] << " "; } cout << endl; } return 0; }
#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...