Submission #1202784

#TimeUsernameProblemLanguageResultExecution timeMemory
1202784AcanikolicNice sequence (IZhO18_sequence)C++20
43 / 100
16 ms1524 KiB
#include <bits/stdc++.h> using namespace std; const int N = 10000 + 10; const int inf = 1e9 + 7; vector<int> g[N]; int n, m; bool check(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(); return ((int)order.size() == x + 1); } 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 l = 0, r = n + m, ans = 0; while(l <= r) { int mid = l + r >> 1; if(check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 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...