Submission #1203341

#TimeUsernameProblemLanguageResultExecution timeMemory
1203341AcanikolicNice sequence (IZhO18_sequence)C++20
100 / 100
507 ms58652 KiB
#include <bits/stdc++.h> using namespace std; const int N = 4e5 + 10; const int inf = 1e9 + 7; vector<int> g[N]; int n, m; vector<int> Solve(int x) { vector<int> in(x + 1); for(int i = min(n, m); i <= x; i++) { if(i >= n) { g[i].push_back(i - n); in[i - n]++; } if(i >= m) { g[i - m].push_back(i); in[i]++; } } queue<int> q; for(int i = 0; i <= x; i++) if(!in[i]) q.push(i); vector<int> order; while(!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for(int j : g[u]) { in[j]--; if(!in[j]) q.push(j); } } for(int i = 0; i <= x; i++) g[i].clear(); vector<int> res(x + 1); int pos = 0; for(int i = 1; i <= x; i++) if(order[i] == 0) pos = i; for(int i = 0; i <= x; i++) res[order[i]] = i - pos; vector<int> ans(x); for(int i = 1; i <= x; i++) ans[i - 1] = res[i] - res[i - 1]; return ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tt; cin >> tt; while(tt--) { cin >> n >> m; int ans = n + m - __gcd(n, m) - 1; cout << ans << "\n"; if(!ans) continue; vector<int> sol = Solve(ans); for(int i = 0; i < ans; i++) cout << sol[i] << " "; cout << "\n"; } }
#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...