Submission #1315520

#TimeUsernameProblemLanguageResultExecution timeMemory
1315520Sam_a17Nice sequence (IZhO18_sequence)C++20
0 / 100
36 ms13092 KiB
#include <bits/stdc++.h> using namespace std; const int N = 4e5 + 10; vector<int> adj[N]; bool used[N]; int n, m, in[N], val[N]; int pt[N]; void clear(int mid) { for (int i = 0; i <= mid; i++) { pt[i] = 0; used[i] = false; adj[i].clear(); in[i] = 0; } } bool check(int mid) { for (int i = 0; i <= mid; i++) { if (i + m <= mid) { adj[i].push_back(i + m); in[i + m]++; } if (i + n <= mid) { adj[i + n].push_back(i); in[i]++; } } queue<int> q; for (int i = 0; i <= mid; i++) { if (!in[i]) { q.push(i); used[i] = true; pt[i] = 0; } } while (!q.empty()) { auto u = q.front(); q.pop(); for (auto i : adj[u]) { pt[i] = max(pt[i], pt[u] + 1); in[i]--; if (!in[i] && !used[i]) { used[i] = true; q.push(i); } } } int cnt = 0; for (int i = 0; i <= mid; i++) { cnt += used[i]; } return cnt == mid + 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { cin >> n >> m; int l = 1, r = N - 10, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } clear(mid); } check(ans); cout << ans << '\n'; int mn = INT32_MAX; for (int i = 1; i <= ans; i++) { pt[i] -= pt[i - 1]; cout << pt[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...