Submission #376087

#TimeUsernameProblemLanguageResultExecution timeMemory
376087ijxjdjdNice sequence (IZhO18_sequence)C++14
100 / 100
481 ms31432 KiB
#include <bits/stdc++.h> #define FR(i, N) for (int i = 0; i < int(N); i++) #define all(x) begin(x), end(x) using namespace std; using ll = long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int getrandom() { return uniform_int_distribution<int>(1, 5000)(rng); } int main() { cin.tie(0); cin.sync_with_stdio(0); int T; cin >> T; FR(iter, T) { int N, M; cin >> N >> M; bool swapped = false; if (max(N,M)%min(N,M) == 0) { if (N >= M) { cout << N-1 << '\n'; for (int i = 0; i < N-1; i++) { cout << 1 << " "; } cout << '\n'; } else { cout << M-1 << '\n'; for (int i = 0; i < M-1; i++) { cout << -1 << " "; } cout << '\n'; } } else { if (N < M) { swap(N, M); swapped = true; } int d = N%M; int mx = N; while (d != 0) { mx = max(mx, d+N); d += N%M; if (d >= M) { d -= M; } if (d == 0) { break; } } vector<int> cntIn(mx, 0); vector<int> pref(mx, 0); int lst = 0; for (int i = 0; i < mx; i++) { if (i+N < mx) { cntIn[i+N]++; } if (i-M >= 0) { cntIn[i-M]++; } } deque<int> deq; for (int i = 0; i < mx; i++) { if (cntIn[i] == 0) { deq.push_back(i); pref[i] = lst++; } } while (deq.size()) { int i = deq.front(); deq.pop_front(); if (i+N<mx) { cntIn[i+N]--; pref[i+N] = lst++; if (cntIn[i+N] == 0) { deq.push_back(i+N); } } if (i-M>=0) { cntIn[i-M]--; pref[i-M] = lst++; if (cntIn[i-M] == 0) { deq.push_back(i-M); } } } for (int i = mx-1; i >=0; i--) { pref[i] -= pref[0]; } if (!swapped) { for (int i = 1; i < mx; i++) { pref[i] *= -1; } } cout << mx - 1 << '\n'; for (int i = 1; i < mx; i++) { cout << pref[i] - pref[i-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...