Submission #1172102

#TimeUsernameProblemLanguageResultExecution timeMemory
1172102sofija6Nice sequence (IZhO18_sequence)C++20
0 / 100
5 ms12104 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 500010 using namespace std; vector<ll> G[MAXN]; ll indeg[MAXN],pref[MAXN],ans[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll t,n,m; cin >> t; while (t--) { cin >> n >> m; ll d=__gcd(n,m); ll len=max(0ll,n+m-d-1); for (ll i=0;i<=len;i++) { G[i].clear(); indeg[i]=pref[i]=ans[i]=0; } for (ll i=0;i+n<=len;i++) { G[i].push_back(i+n); indeg[i+n]++; } for (ll i=0;i+m<=len;i++) { G[i+m].push_back(i); indeg[i]++; } queue<ll> q; for (ll i=0;i<=len;i++) { if (!indeg[i]) q.push(i); } while (!q.empty()) { ll i=q.front(); q.pop(); for (ll next : G[i]) { indeg[next]--; pref[next]=min(pref[next],pref[i]-1); if (!indeg[next]) q.push(next); } } cout << len << "\n"; set<ll> s; ll toadd=0; for (ll i=1;i<=len;i++) { pref[i]+=toadd; if (pref[i]==pref[i-1]) { pref[i]++; toadd++; } ans[i]=pref[i]-pref[i-1]; s.insert(ans[i]); } for (ll i=1;i<=len;i++) cout << ans[i] << " "; cout << "\n"; } 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...