Submission #1185162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185162		PieArmy	Nice sequence (IZhO18_sequence)	C++20	20 / 100	140 ms	21012 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;
	if(pos-m>=0){
		if(pref[pos-m]==dal)return false;
		if(pref[pos-m]==unvis&&!dfs(pos-m,mx,base))return false;
		res=max(res,pref[pos-m]+1);
	}
	if(pos+n<=mx){
		if(pref[pos+n]==dal)return false;
		if(pref[pos+n]==unvis&&!dfs(pos+n,mx,base))return false;
		res=max(res,pref[pos+n]+1);
	}
	pref[pos]=res;
	return true;
}

bool f(int x){
	for(int i=0;i<=x;i++){
		pref[i]=unvis;
	}
	ll base=-unvis;
	for(int i=0;i<=x;i++){
		if(pref[i]!=unvis)continue;
		if(!dfs(i,x,base))return false;
		base+=1e7;
	}
	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;
	}
}

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