Submission #379068

#	Time	Username	Problem	Language	Result	Execution time	Memory
379068		YJU	Nice sequence (IZhO18_sequence)	C++14	100 / 100	561 ms	47084 KiB

sequence

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e6+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define ALL(_a) _a.begin(),_a.end()
#define SZ(_a) (ll)_a.size()

ll dg[N],p[N],n,m,t,x;

bool ck(ll L){
	memset(dg,0,sizeof(dg));
	REP(i,L+1){
		if(i>=n)++dg[i-n];
		if(i+m<=L)++dg[i+m];
	}

	queue<ll> que;
	REP(i,L+1)if(dg[i]==0)que.push(i),p[i]=0;
	ll ptr=0;
	while(SZ(que)){
        x=que.front();que.pop();
        p[x]=++ptr;
        if(x>=n){
			if(--dg[x-n]==0)que.push(x-n);
        }
        if(x+m<=L){
			if(--dg[x+m]==0)que.push(x+m);
        }
	}
	REP(i,L+1)if(dg[i])return 0;
	return 1;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		ll l=n+m-__gcd(n,m)-1;
		ck(l);
		cout<<l<<"\n";
		if(l==0)continue;
		if(l)REP1(i,l)cout<<p[i]-p[i-1]<<" \n"[i==l];
	}
	return 0;
}

• 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