Submission #1185165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185165		PieArmy	Nice sequence (IZhO18_sequence)	C++20	100 / 100	477 ms	60980 KiB

sequence

#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;
}

int gcd(int a,int b){
	if(a<b)swap(a,b);
	if(b==0)return a;
	return gcd(b,a%b);
}

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;
	}*/
	int l=n+m-gcd(n,m)-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;
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24