Submission #493960

#	Time	Username	Problem	Language	Result	Execution time	Memory
493960		leaked	Devil's Share (RMI19_devil)	C++14	0 / 100	1590 ms	4340 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);

using namespace std;
vec<vec<int>> vc;
vec<int>cnt(5,0);
vec<int> cr;
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;
}
void rec(int i,int mx){
    vc.pb(cr);
    for(int j=0;j<=min(3,mx+1);j++){
        ++cnt[j];
        if(cnt[j]<=3){
            cr.pb(j);
            rec(i+1,max(j,mx));
            cr.pop_back();
        }
        --cnt[j];
    }
}

signed main(){
    fast_rmi;
    rec(0,-1);
    int t;
    cin>>t;
    while(t--){
        vec<int> cnt(10,0);
        int ok=1,sum=0;
        int k;
        cin>>k;
        for(int i=1;i<10;i++)
            cin>>cnt[i-1],ok&=(i>=4?cnt[i-1]==0:1),sum+=cnt[i-1];
        if(!ok){

        }
        string ans;
        string mn="z";
        for(auto &z : vc){
            if(sum!=sz(z))
                continue;
            vec<int> p(4,0);
            iota(all(p),0);
            do{
                int ok=1;
                vec<int> ent=cnt;
                string s;
                for(auto &q : z){
                    if(!ent[p[q]]){
                        ok=0;
                        continue;
                    }
                    --ent[p[q]];
                    s+=char('1'+p[q]);
                }
                if(!ok)
                    continue;
                string me=find_max(s,k);
                if(me<mn){
                    mn=me;
                    ans=s;
                }
            }while(next_permutation(all(p)));
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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