oj.uz

Submission #234013

# Submission time Handle Problem Language Result Execution time Memory
234013 2020-05-22T19:23:00 Z Sorting Devil's Share (RMI19_devil) C++14
13 / 100
 1500 ms 504 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 504 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 504 KB Output is correct
2 Execution timed out 1572 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -