제출 #1185163

#제출 시각아이디문제언어결과실행 시간메모리
1185163PieArmyNice sequence (IZhO18_sequence)C++20
100 / 100
1180 ms63492 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

const ll dal=10000000000000000,unvis=10000000000000001;

int n,m;
ll pref[400023];

int dfs(int pos,int mx,ll base){
	pref[pos]=dal;
	ll res=base;
	int sum=1;
	if(pos-m>=0){
		if(pref[pos-m]==dal)return false;
		if(pref[pos-m]==unvis){
			int x=dfs(pos-m,mx,base);
			sum+=x;
			if(!x)return 0;
		}
		res=max(res,pref[pos-m]+1);
	}
	if(pos+n<=mx){
		if(pref[pos+n]==dal)return false;
		if(pref[pos+n]==unvis){
			int x=dfs(pos+n,mx,base);
			sum+=x;
			if(!x)return 0;
		}
		res=max(res,pref[pos+n]+1);
	}
	pref[pos]=res;
	return sum;
}

bool f(int x){
	for(int i=0;i<=x;i++){
		pref[i]=unvis;
	}
	ll base=0;
	for(int i=0;i<=x;i++){
		if(pref[i]!=unvis)continue;
		int y=dfs(i,x,base);
		if(y==0)return false;
		base+=y;
	}
	return true;
}

void solve(){
	cin>>n>>m;
	int l=max(n,m)-1,r=n+m-1;
	while(l<r){
		int mi=(l+r+1)/2;
		if(f(mi))l=mi;
		else r=mi-1;
	}
	f(l);
	for(int i=l;i>=1;i--){
		pref[i]-=pref[i-1];
	}
	cout<<l<<endl;
	for(int i=1;i<=l;i++){
		cout<<pref[i]<<" ";
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int t;cin>>t;
	while(t--){
		solve();
		cout<<endl;
	}
}
#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...