Submission #844867

#	Time	Username	Problem	Language	Result	Execution time	Memory
844867		Darren0724	Nice sequence (IZhO18_sequence)	C++17	100 / 100	344 ms	37396 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()

int check(int a,int b,int k){
    vector<int> s(k+1);
    int now=0;
    while(1){
        s[now]=1;
        if(now>=b){
            now-=b;
        }
        else{
            now+=a;
        }
        if(now==0){
            return 1;
        }
        if(now>k||s[now]==1){
            return 0;
        }
    }
}
void solve(){
    int a,b;cin>>a>>b;
    int l=0,r=a+b+5;
    while(r-l>1){
        int m=(l+r)>>1;
        if(check(a,b,m)){
            r=m;
        }
        else{
            l=m;
        }
    }
    cout<<l<<endl;
    vector<int> ans(l+1);
    vector<int> in(l+1);
    for(int i=0;i<=l;i++){
        if(i>=a){
            in[i-a]++;
        }
        if(i+b<=l){
            in[i+b]++;
        }
    }
    queue<int> q;
    for(int i=0;i<=l;i++){
        if(in[i]==0){
            q.push(i);
        }
    }
    int cnt=1;
    while(q.size()){
        int p=q.front();
        q.pop();
        ans[p]=cnt++;
        if(p>=a){
            in[p-a]--;
            if(in[p-a]==0){
                q.push(p-a);
            }
        }
        if(p+b<=l){
            in[p+b]--;
            if(in[p+b]==0){
                q.push(p+b);
            }
        }
    }
    for(int i=1;i<=l;i++){
        cout<<ans[i]-ans[i-1]<<' ';
    }
    cout<<endl;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }

    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