Submission #680760

#TimeUsernameProblemLanguageResultExecution timeMemory
680760AndreyPavlovNice sequence (IZhO18_sequence)C++17
100 / 100
1169 ms82164 KiB
/* Includes */ #include <bits/stdc++.h> /* Using libraries */ using namespace std; /* Defines */ #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ld long double #define pb push_back #define sz(a) (int)a.size() #define forn(i, n) for (int i = 0; i < n; ++i) #define pii pair <int, int> #define vec pt #define vc vector #define all(a) a.begin(), a.end() #define int long long const int N = 5e5; vc <int> g[N], t; int used[N]; void dfs(int u) { used[u] = 1; for (int v: g[u]) { if (!used[v]) dfs(v); } t.pb(u); } void solve () { int n, m; cin >> n >> m; int len = n + m - 1 - __gcd(n, m); for (int i = 0; i <= len; ++i) g[i].clear(), used[i] = 0; t.clear(); for (int i = 0; i <= len; ++i) { if (i >= m) g[i].pb(i - m); if (i >= n) g[i - n].pb(i); } for (int i = 0; i <= len; ++i) { if (!used[i]) dfs(i); } vc <int> l(len + 1); int cnt = 0; for (int u : t) { l[u] = cnt++; } cout << len << '\n'; vc <int> p(len); for (int i = 1; i <= len; ++i) { p[i - 1] = l[i] - l[i - 1]; } for (int i = 0; i < len; ++i) { cout << p[i] << ' '; } cout << '\n'; } /* Starting and precalcing */ signed main() { fast; cout << fixed << setprecision(12); int t = 1; 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...