Submission #493900

#	Time	Username	Problem	Language	Result	Execution time	Memory
493900		leaked	Devil's Share (RMI19_devil)	C++14	0 / 100	117 ms	1360 KiB

devil

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

//#pragma GCC optimize("Ofast")

using namespace std;
typedef pair<int,int> pii;
int c[10];
string find_max(string ans,int k){
    string me=ans.substr(0,k);
    for(int i=0;i+k-1<sz(ans);i++){
        string w=ans.substr(i,k);
        me=max(me,w);
    }
    return me;
}
string solve(int k){
    string suf;
    string ans;
    int how=0;
    int r=-1;
    for(int d=9;d>=0;d--){
        how+=c[d];
        if(how>=k){
            r=d;
            break;
        }
    }
    for(int j=r+1;j<=9;j++){
        while(c[j]--)
            suf+=char('0'+j);
    }
    /// control points is r
    vec<vec<int>> vc(c[r],vec<int>());
    for(int i=0;i<c[r];i++){
        vc[i].pb(r);
    }
    int n=c[r];
    vec<int> prior(n);
    for(int i=0;i<n-1;i++){
        prior[i]=(sz(vc[i])==1?0:1);
    }
    vec<int>p(n);
    iota(all(p),0);
    for(int d=0;d<r;d++){
        int cnt=c[d]/n;
        vec<bool>placed(n,0);
        while(cnt--){
            for(auto &z : vc)
                z.pb(d);
        }
        c[d]%=n;
        for(int i=n-1;i>=0 && c[d];i--,c[d]--)
            vc[p[i]].pb(d),placed[p[i]]=1;
        vec<int> np=p;
        vec<int>nprior(n);
        sort(all(np),[&](int i,int j){
             return (prior[i]!=prior[j]?prior[i]<prior[j]:placed[i]>placed[j]);
        });
        nprior[np[0]]=0;
        for(int i=1;i<n;i++){
            int f=np[i],s=np[i-1];
            nprior[f]=nprior[s];
            if(prior[f]==prior[s] && placed[f]==placed[s])
                continue;
            nprior[f]++;
        }
        p=np;
        prior=nprior;
    }
//    cout<<"CONTROL "<<r<<endl;
    for(auto &z : vc){
//        reverse(all(z));
        for(auto &q : z)
            ans+=char('0'+q);
    }
//    cout<<"ANSWER "<<find_max(ans+suf,k)<<'\n';
    return ans+suf;
}
signed main(){
    fast_rmi;
    int q;
    cin>>q;
    while(q--){
        int k;
        cin>>k;
        c[0]=0;
        for(int i=1;i<10;i++)
            cin>>c[i];
//        cout<<"W "<<endl;
        cout<<solve(k)<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44