Submission #636790

#	Time	Username	Problem	Language	Result	Execution time	Memory
636790		ogibogi2004	Devil's Share (RMI19_devil)	C++14	0 / 100	107 ms	1300 KiB

devil

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll D[10],k;
void solve1()
{
    vector<int>digits;
    for(int i=1;i<10;i++)
    {
        for(int j=0;j<D[i];j++)
        {
            digits.push_back(i);
        }
    }
    vector<int>ans;
    ll min_of_max=(ll)1e18;
    ll pw10=1;
    for(int j=0;j<k;j++)pw10*=10;
    do
    {
        ll num=0,biggestnum=0;
        for(int j=0;j<k;j++)
        {
            num=num*10+digits[j];
        }
        biggestnum=num;
        for(int j=k;j<digits.size();j++)
        {
            num*=10;
            num+=digits[j];
            num%=pw10;
            biggestnum=max(biggestnum,num);
        }
        if(biggestnum<min_of_max)
        {
            ans=digits;
            min_of_max=biggestnum;
        }
    }while(next_permutation(digits.begin(),digits.end()));
    for(auto xd:ans)cout<<xd;
    cout<<endl;
    cout<<min_of_max<<endl;
}
void solve2()
{
    string ans="";
    deque<int>dq;
    for(int i=1;i<=9;i++)
    {
        for(int j=0;j<D[i];j++)
        {
            dq.push_back(i);
        }
    }
    while(!dq.empty())
    {
        ans+=char('0'+dq.back());
        dq.pop_back();
        if(!dq.empty())
        {
            ans+=char('0'+dq.front());
            dq.pop_front();
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}
void solve3()
{
    if(D[2]==0)
    {
        for(int i=0;i<k;i++)cout<<1;
        cout<<endl;
        return;
    }
    vector<int>v;
    int sum=0,b=k;
    vector<int>pref;
    for(;;)
    {
        //for(auto xd:v)
        //    cout<<xd<<" ";
        //cout<<endl;
        bool found=0;
        int j1;
        int cntb=v.size();
        for(int j=min((ll)(k-sum-v.size()-1),(ll)(b));j>=0;j--)
        {
            //cout<<"^^ "<<j<<endl;
            int max2=(D[1]/(cntb+1))*(sum+j);
            int t=D[1]%(cntb+1);
            //cout<<max2<<" "<<t<<endl;
            if(t==0)
            {
                if(v.size()>0&&j==v[0])max2+=k-2;
                else max2+=k-1;
            }
            else
            {
                max2+=k-1;
                //cout<<"% "<<max2<<endl;
                //if(v.size()>0&&j==v[0])max2+=k-2;
                //else max2+=k-1;
            }
            //cout<<"eho\n";
            if(D[2]<=max2)
            {
                //cout<<j<<" ok\n";
                found=1;j1=j;
                continue;
            }
            else
            {
                break;
            }
        }
        //cout<<"?\n";
        if(!found)
        {
            //v.push_back(k-sum-v.size());
            break;
        }
        else
        {
            v.push_back(j1);
            b=j1;
            sum+=j1;
            if(pref.size()>0)pref.push_back(v.back()+pref.back());
            else pref.push_back(v.back());
            continue;
        }
    }
    int d1=D[1];
    int d2=D[2];
    for(int j=0;;j++)
    {
        for(int l=0;l<v[j%v.size()]&&d2>0;l++)
        {
            cout<<2;
            d2--;
        }
        cout<<1;
        d1--;
        if(d1==1)
        {
            cout<<1;
            d1--;
        }
        if(d1==0)
        {
            while(d2>0)
            {
                cout<<2;
                d2--;
            }
            cout<<endl;
            break;
        }
    }
    /*string ans="";
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<v[i];j++)ans+="2";
        ans+="1";
    }
    for(int i=0;i<k;i++)cout<<ans[i];
    cout<<endl;*/
}
int main()
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);*/
    int t;
    cin>>t;
    while(t--)
    {
        cin>>k;
        for(int i=1;i<=9;i++)cin>>D[i];
        if(D[3]==0&&D[4]==0&&D[5]==0&&D[6]==0&&D[7]==0&&D[8]==0&&D[9]==0)solve3();
        else if(k==2)solve2();
        else solve1();
    }
return 0;
}

Compilation message (stderr)

devil.cpp: In function 'void solve1()':
devil.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int j=k;j<digits.size();j++)
      |                     ~^~~~~~~~~~~~~~

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