竞赛讨论区 > 牛客寒假集训营 6 G 90% 求差错
头像
shyiaw
发布于 03-16 11:48
+ 关注

牛客寒假集训营 6 G 90% 求差错

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb push_back
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
void solve(){
    int n,s,k;cin>>n>>s>>k;
    vector<int> ans;
    if(k==0){
        rep(i,1,n-1){
            if(s<1){
                cout<<-1<<endl;
                return;
            }
            ans.pb(1);s--;
        }
        if(s<1){
            cout<<-1<<endl;
            return;
        }
        ans.pb(s);
    }
    else{
        if(n<2*k+1){
            cout<<-1<<endl;
            return;
        }
        else if(n==2*k+1){
            int a=k,b=k+1,c=s;
            int x,y;
            int d=exgcd(a,b,x,y);
            if(s%d){
                cout<<-1<<endl;
                return;
            }
            a/=d,b/=d,c/=d;
            exgcd(a,b,x,y);
            x*=c,y*=c;
            //cout<<x<<y<<endl;
            bool fl=false;
            vector<int> choice={-x/b,-x/b+1};
            for(auto k:choice){
                int curx=x+b*k;
                int cury=y-a*k;
                if(curx>0&&cury>0&&cury>curx){
                    x=curx,y=cury;
                    fl=true;
                    break;
                }
            }
            if(!fl){
                cout<<-1<<endl;
                return;
            }
            rep(i,1,n){
                if(i&1) ans.pb(y);
                else ans.pb(x);
            }
        }
        else{
            rep(i,1,2*k+1){
                int v=i%2+1;
                if(s<v){
                    cout<<-1<<endl;
                    return;
                }
                ans.pb(v),s-=v;
            }
            if(n-2*k-1==2&&s==3){
                ans.pb(2),ans.pb(1);
            }
            else{
                rep(i,2*k+2,n){
                    if(s<1){
                        cout<<-1<<endl;
                        return;
                    }
                    if(i!=n) ans.pb(1),s--;
                    else ans.pb(s);
                }
            }
        }
    }
    for(auto v:ans) cout<<v<<" ";
    cout<<endl;
}
int main(){
    IOS
    int t=1; cin>>t;
    while(t--) solve();
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐