This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<bool> used;
vector<int> tout;
int T = 0;
void dfs(int u, int N, int M) {
used[u] = true;
if (u - M >= 0 && !used[u - M]) {
dfs(u - M, N, M);
}
if (u + N < (int)used.size() && !used[u + N]) {
dfs(u + N, N, M);
}
tout[u] = T++;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int N, M;
cin >> N >> M;
int l = -1, r = 2 * (N + M) + 1;
vector<int> answer;
while (r > l + 1) {
int mid = (l + r) / 2;
used.assign(mid + 1, false);
tout.resize(mid + 1);
used.assign(mid + 1, false);
for (int i = 0; i <= mid; i++) {
if (!used[i]) {
dfs(i, N, M);
}
}
bool good = true;
for (int i = 0; i <= mid; i++) {
if (i + N <= mid && tout[i + N] > tout[i]) {
good = false;
}
if (i - M >= 0 && tout[i - M] > tout[i]) {
good = false;
}
}
if (good) {
l = mid;
answer.resize(mid);
for (int i = 0; i < mid; i++) {
answer[i] = tout[i + 1] - tout[i];
}
} else {
r = mid;
}
}
cout << l << "\n";
for (int i = 0; i < l; i++) {
cout << answer[i] << " \n"[i + 1 == l];
}
}
}
# | 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... |