Submission #689407

#TimeUsernameProblemLanguageResultExecution timeMemory
689407gesghaNice sequence (IZhO18_sequence)C++17
76 / 100
2072 ms62216 KiB
#include <bits/stdc++.h> #define fr(x, l, r) for (int x = l; x <= r; x++) #define rf(x, l, r) for (int x = l; x >= r; x--) #define fe(x, y) for (auto& x : y) #define fi first #define se second #define m_p make_pair #define pb push_back #define pw(x) (ll(1) << ull(x)) #define all(x) (x).begin(), x.end() #define sz(x) (int)x.size() #define mt make_tuple using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef pair<ld, ld> pld; template <typename T> using ve = vector<T>; template <typename T> bool umn(T& a, T b) {return a > b ? a = b, 1 : 0;} template <typename T> bool umx(T& a, T b) {return a < b ? a = b, 1 : 0;} const ll OO = 1e18; const int oo = 1e9; const int mod = 1e9 + 7; const int P = 29; const ld eps = 0.00000001; const int N = 4e5 + 10; const bool TEST = 1; void precalc() {} int G[N][10]; int sz[N]; int a[N]; int sz_A; bool vis[N]; int ptr[N]; void dfs(int v) { vis[v] = 1; fr(i, 0, sz[v] - 1) if (!vis[G[v][i]]) dfs(G[v][i]); a[sz_A++] = v; } bool visn[N]; bool is_cycle(int v) { a[sz_A++] = v; visn[v] = 1; vis[v] = 1; bool ok = 0; fr(i, 0, sz[v] - 1) { if (visn[G[v][i]]) return 1; if (!vis[G[v][i]]) { ok |= is_cycle(G[v][i]); if (ok) return 1; } } return 0; } bool can(int n, int m, int k) { sz_A = 0; fr(i, 0, k) sz[i] = ptr[i] = vis[i] = 0; fr(i, 1, k) { if (i + n - 1 <= k) G[i + n - 1][sz[i + n - 1]++] = (i - 1); if (i + m - 1 <= k) G[i - 1][sz[i - 1]++] = (i + m - 1); } bool ok = 0; fr(i, 0, k) { if (vis[i]) continue; ok |= is_cycle(i); fr(i, 0, sz_A - 1) visn[a[i]] = 0; sz_A = 0; if (ok) return 0; } return 1; } int pr[N]; int A[N]; void solve(int TST) { int n, m; cin >> n >> m; int l = max(n, m) - 1; int r = 2 * max(n, m); while(l < r) { int tm = (l + r + 1) >> 1; if (can(n, m, tm)) l = tm; else r = tm - 1; } fr(i, 0, l) { sz[i] = 0; ptr[i] = 0; } sz_A = 0; fr(i, 0, l) vis[i] = 0; fr(i, 1, l) { if (i + n - 1 <= l) G[i + n - 1][sz[i + n - 1]++] = (i - 1); if (i + m - 1 <= l) G[i - 1][sz[i - 1]++] = (i + m - 1); } fr(i, 0, l) if (!vis[i]) dfs(i); reverse(a, a + sz_A); int cnt = 0; fr (i, 0, sz_A - 1) pr[a[i]] = cnt++; fr(i, 1, l) A[i] = pr[i] - pr[i - 1]; cout << l << endl; fr(i, 1, l) cout << A[i] << ' '; cout << endl; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int q = 1; if (TEST) cin >> q; precalc(); for (int z = 1; z <= q; z++) { solve(z); } 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...