Submission #173963

#TimeUsernameProblemLanguageResultExecution timeMemory
173963mcdx9524Nice sequence (IZhO18_sequence)C++14
20 / 100
3 ms636 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200 + 7; int n, m; vector <int> p; vector <int> ord; vector <int> g[N]; bool used[N]; int col[N]; bool cycle(int v) { col[v] = 1; for (int u : g[v]) { if (col[u] == 0) { if (cycle(u)) { return true; } } else if (col[u] == 1) { return true; } } col[v] = 2; return false; } void dfs(int v) { if (used[v] == true) { return; } used[v] = true; for (int u : g[v]) { dfs(u); } ord.push_back(v); } bool build(int sz) { ord.clear(); for (int i = 0; i < N; i++) { g[i].clear(); used[i] = false; col[i] = 0; } for (int i = 1; i <= sz; i++) { // p[i] - p[i - n] < 0 // p[i] < p[i - n] if (i - n >= 0) { g[i - n].push_back(i); } // p[i] > p[i - m] if (i - m >= 0) { g[i].push_back(i - m); } } for (int i = 0; i <= sz; i++) { if (cycle(i)) { return false; } } for (int i = 0; i <= sz; i++) { dfs(i); } p.resize(sz + 1, 0); int cur = sz; reverse(ord.begin(), ord.end()); for (int x : ord) { p[x] = cur--; } for (int i = 0; i <= sz; i++) { if (!p[i]) { p[i] = cur--; } } return true; } void solve() { cin >> n >> m; int l = max(n, m) - 1, r = n + m + 7; int ans = l; while (l <= r) { int md = (l + r) / 2; if (build(md)) { l = md + 1; ans = md; } else { r = md - 1; } } build(ans); cout << ans << '\n'; for (int i = 1; i <= ans; i++) { cout << p[i] - p[i - 1] << ' '; } cout << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { solve(); } 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...