Submission #234013

#	Time	Username	Problem	Language	Result	Execution time	Memory
234013		Sorting	Devil's Share (RMI19_devil)	C++14	13 / 100	1578 ms	504 KiB

devil

#include <bits/stdc++.h>

using namespace std;

int d[10], k;

string largest_string, answer;
string s;

string get_largest_substring(const string &s){
    string answer = "";
    for(int i = 0; i < k; ++i)
        answer += s[i];

    for(int i = k; i < (int)s.size(); ++i){
        string curr = "";
        for(int j = i - k + 1; j <= i; ++j)
            curr += s[j];

        if(curr > answer)
            answer = curr;
    }
    return answer;
}

void recursion(int cnt){
    if(s.size() >= k){
        string curr = s.substr(s.size() - k, k);
        if(curr > largest_string)
            return;
    }

    if(!cnt){
        largest_string = get_largest_substring(s);
        answer = s;
        return;
    }

    for(int i = 1; i <= 9; ++i){
        if(d[i]){
            --d[i];
            s += (char)(i + '0');

            recursion(cnt - 1);

            s.erase((int)s.size() - 1, 1);
            ++d[i];
        }
    }
}

void read(){
    cin >> k;
    
    for(int i = 1; i <= 9; ++i)
        cin >> d[i];
}

void solve_test(){
    read();

    int cnt = 0;
    for(int i = 1; i <= 9; ++i)
        cnt += d[i];

    answer = "";
    largest_string = "";
    for(int i = 0; i < k; ++i)
        largest_string += (char)('9' + 1);
    s = "";

    recursion(cnt);

    cout << answer << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve_test();
}

Compilation message (stderr)

devil.cpp: In function 'void recursion(int)':
devil.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size() >= k){
        ~~~~~~~~~^~~~

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