This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// I stand with PALESTINE
//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
random_device rd;
mt19937 mt(rd());
int rand(int l, int r) {
uniform_int_distribution<int> dist(l, r);
return dist(mt);
};
void out(vector<int> a, bool minus = false) {
cout << a.size() << '\n';
if (a.empty()) return;
for (int x: a) cout << x * (minus ? -1 : 1) << ' ';
cout << '\n';
}
int nn, mm;
vector<int> solve(int n, int m) {
// n >= m
if (n % m == 0) return vector(n - 1, 1);
if (m == 2) {
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i % 2 ? inf : -(inf - 1);
return a;
}
vector<int> a(m - 1, -100);
int ln = m - 1;
while (true) {
ll lxm = -1000 * ln, rxm = 1000 * ln;
ll lxp = -1000 * ln, rxp = 1000 * ln;
if (ln >= m - 1) {
ll sum = 0;
for (int i = ln - m + 1; i < ln; i++) sum += a[i];
// sum + x >= 0
// x >= -sum
lxp = max(lxp, -sum);
}
if (ln >= n - 1) {
ll sum = 0;
for (int i = ln - n + 1; i < ln; i++) sum += a[i];
rxm = min(rxm, -sum);
}
ll l = max(lxm, lxp), r = min(rxm, rxp);
if (l > r) break;
a.emplace_back(rand(l, r));
ln++;
}
return a;
}
void solve() {
int n, m;
cin >> n >> m;
if (n >= m) out(solve(n, m));
else out(solve(m, n), true);
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int q = 1;
cin >> q;
while (q--) {
solve();
// cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |