제출 #379028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379028		YJU	Nice sequence (IZhO18_sequence)	C++14	0 / 100	12 ms	3436 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=2e5+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));
	memset(p,-1,sizeof(p));
	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;
	while(SZ(que)){
        x=que.front();que.pop();
        if(x>=n){
			p[x-n]=max(p[x-n],p[x]+1);
			--dg[x-n];
			if(dg[x-n]==0)que.push(x-n);
        }
        if(x+m<=L){
			p[x+m]=max(p[x+m],p[x]+1);
			--dg[x+m];
			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=0,r=2*(n+m);
		while(r-l>1){
			ll mid=(l+r)>>1;
			if(ck(mid)){
				l=mid;
			}else{
				r=mid;
			}
		}
		ck(l);
		cout<<l<<"\n";
		REP1(i,l)cout<<p[i]-p[i-1]<<" \n"[i==l];
	}
	return 0;
}

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