제출 #1315519

#제출 시각아이디문제언어결과실행 시간메모리
1315519Sam_a17Nice sequence (IZhO18_sequence)C++20
0 / 100
36 ms13148 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 = 0; i < ans; i++) { mn = min(mn, pt[i]); } for (int i = 0; i < ans; i++) { cout << pt[i] + mn + 1 << " "; } 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...