#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
vector<int> adj[N];
bool used[N];
int n, m, in[N], val[N];
int pt[N];
void clear(int mid)
{
for (int i = 0; i <= mid; i++)
{
pt[i] = 0;
used[i] = false;
adj[i].clear();
in[i] = 0;
}
}
bool check(int mid)
{
for (int i = 0; i <= mid; i++)
{
if (i + m <= mid)
{
adj[i].push_back(i + m);
in[i + m]++;
}
if (i + n <= mid)
{
adj[i + n].push_back(i);
in[i]++;
}
}
queue<int> q;
for (int i = 0; i <= mid; i++)
{
if (!in[i])
{
q.push(i);
used[i] = true;
pt[i] = 0;
}
}
while (!q.empty())
{
auto u = q.front();
q.pop();
for (auto i : adj[u])
{
pt[i] = max(pt[i], pt[u] + 1);
in[i]--;
if (!in[i] && !used[i])
{
used[i] = true;
q.push(i);
}
}
}
int cnt = 0;
for (int i = 0; i <= mid; i++)
{
cnt += used[i];
}
return cnt == mid + 1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
int l = 1, r = N - 10, ans = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
clear(mid);
}
check(ans);
cout << ans << '\n';
int mn = INT32_MAX;
for (int i = 0; i < ans; i++)
{
mn = min(mn, pt[i]);
}
for (int i = 0; i < ans; i++)
{
cout << pt[i] + mn + 1 << " ";
}
cout << '\n';
}
return 0;
}
| # | 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... |