Submission #689412

#TimeUsernameProblemLanguageResultExecution timeMemory
689412gesghaNice sequence (IZhO18_sequence)C++17
100 / 100
1043 ms48404 KiB
#include <bits/stdc++.h>

#define fr(x, l, r) for (int x = l; x <= r; x++)
#define rf(x, l, r) for (int x = l; x >= r; x--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define m_p make_pair
#define pb push_back
#define pw(x) (ll(1) << ull(x))
#define all(x) (x).begin(), x.end()
#define sz(x) (int)x.size()
#define mt make_tuple

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;

template <typename T>
using ve = vector<T>;

template <typename T>
bool umn(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T>
bool umx(T& a, T b) {return a < b ? a = b, 1 : 0;}

const ll OO = 1e18;
const int oo = 1e9;
const int mod = 1e9 + 7;
const int P = 29;
const ld eps = 0.00000001;
const int N = 4e5 + 10;
const bool TEST = 1;

void precalc() {}

int G[N][4];
int sz[N];
int a[N];
int sz_A;
bool vis[N];
int ptr[N];
int n, m, k;


void dfs(int v) {
    vis[v] = 1;
    
    if (v + m <= k && !vis[v + m]) dfs(v + m);
    if (v - n >= 0 && !vis[v - n]) dfs(v - n);
    a[sz_A++] = v;
}


bool visn[N];

bool is_cycle(int v) {
    a[sz_A++] = v;
    visn[v] = 1;
    vis[v] = 1;
    bool ok = 0;
    if (v + m <= k) {
        if (visn[v + m]) return 1;
        if (!vis[v + m]) {
            ok |= is_cycle(v + m);
            if (ok) return 1;
        }
    }
    if (v - n >= 0) {
        if (visn[v - n]) return 1;
        if (!vis[v - n]) {
            ok |= is_cycle(v - n);
            if (ok) return 1;
        }
    }
    return 0;
}


bool can(int n, int m, int k) {
    ::n = n;
    ::m = m;
    ::k = k;
    sz_A = 0;
    fr(i, 0, k) sz[i] = ptr[i] = vis[i] = 0;

    // fr(i, 1, k) {
    //     if (i + n - 1 <= k) G[i + n - 1][sz[i + n - 1]++] = (i - 1);
    //     if (i + m - 1 <= k) G[i - 1][sz[i - 1]++] = (i + m - 1);
    // }
    bool ok = 0;
    fr(i, 0, k) {
        if (vis[i]) continue;
        ok |= is_cycle(i);
        fr(i, 0, sz_A - 1) visn[a[i]] = 0;
        sz_A = 0;
        if (ok) return 0;
    }
    return 1;
}
int pr[N];
int A[N];

void solve(int TST) {
    int n, m;
    cin >> n >> m;

    int l = max(n, m) - 1;
    int r = n + m;

    while(l < r) {
        int tm = (l + r + 1) >> 1;
        if (can(n, m, tm)) l = tm;
        else r = tm - 1;
    }
    ::k = l;
    ::n = n;
    ::m = m;

    fr(i, 0, l) {
        sz[i] = 0;
        ptr[i] = 0;
    }
    sz_A = 0;
    fr(i, 0, l) vis[i] = 0;

    // fr(i, 1, l) {
    //     if (i + n - 1 <= l) G[i + n - 1][sz[i + n - 1]++] = (i - 1);
    //     if (i + m - 1 <= l) G[i - 1][sz[i - 1]++] = (i + m - 1);
    // }
    fr(i, 0, l) if (!vis[i]) dfs(i);
    reverse(a, a + sz_A);

    int cnt = 0;
    fr (i, 0, sz_A - 1) {
        pr[a[i]] = cnt++;
    }
    fr(i, 1, l) A[i] = pr[i] - pr[i - 1];

    cout << l << endl;
    fr(i, 1, l) cout << A[i] << ' ';
    cout << endl;
}


int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int q = 1;
    if (TEST) cin >> q;
    precalc();
    for (int z = 1; z <= q; z++) {
        solve(z);
    }
    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...