제출 #1133186

#제출 시각아이디문제언어결과실행 시간메모리
1133186MuhammetNice sequence (IZhO18_sequence)C++17
0 / 100
2093 ms33760 KiB
#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

const int N = 1e5+5;

ll T, n, m, b;

vector <int> vis, a;

vector <vector <int>> v;

bool tr;

int df(int x){
	// if(!x) return x;
	if(vis[x]) return a[x];
	for(auto i : v[x]){
		a[x] = max(a[x], df(i)+1);
	}
	vis[x] = true;
	return a[x];
}

void dfs(int x){
	vis[x] = b;
	for(auto i : v[x]){
		if(vis[i]){
			if(vis[i] == vis[x]) tr = 1;
			continue;
		}
		dfs(i);
	}
	return;
}

bool f(int x){
	v.clear();
	v.resize(x+1);
	vis.assign(x+1,0);
	tr = 0;
	b = 0;
	for(int i = 1; i <= x; i++){
		if(i-n > 0) v[i-n].push_back(i);
		if(i-m >= 0) v[i].push_back(i-m);
	}
	for(int i = 1; i <= x; i++){
		if(vis[i]) continue;
		b++;
		dfs(i);
	}
	if(tr) return false;
	vis.assign(x+1,0);
	vis[0] = true;
	a.assign(x+1,0);
	for(int i = 1; i <= x; i++){
		df(i);
	}
	return true;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> T;
	while(T--) {
		cin >> n >> m;
		int l = 1, r = n+m, k = 0;
		while(l <= r) {
			int md = (l + r) / 2;
			if(f(md)) {
				l = md+1;
				k = md;
			}
			else {
				r = md-1;
			}
		}
		cout << k-1 << '\n';
		f(k);
		for(int i = 2; i <= k; i++){
			cout << a[i]-a[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...