Submission #685084

#	Time	Username	Problem	Language	Result	Execution time	Memory
685084		Bliznetc	Devil's Share (RMI19_devil)	C++17	100 / 100	95 ms	6024 KiB

devil

#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC target("avx2")

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

int a[10];

int get_max() {
    int num = 9;
    while (num >= 1 && a[num] == 0) {
        num--;
    }
    return num;
}

int get_min() {
    int num = 1;
    while (num <= 9 && a[num] == 0) {
        num++;
    }
    return num;
}

void solve(){
    int k;
    cin >> k;
    int n = 0;
    for (int i = 1; i <= 9; i++) {
        cin >> a[i];
        n += a[i];
    }
    int nn = n;
    int ans[n + 7];
    for (int i = 1; i <= n; i++) {
        ans[i] = 0;
    }
    for (int i = 1; i <= k - 1; i++) {
        int num = get_max();
        ans[n] = num;
        a[num] -= 1;
        n--;
    }

    int mx = get_max();
    vector <string> vec;
    for (int i = 1; i <= a[mx]; i++) {
        vec.pb (to_string(mx));
    }
    a[mx] = 0;
    queue <string> q;
    for (int i = 1; i < 10; i++) {
        while (a[i]--) {
            q.push(to_string(i));
        }
    }

    int num = vec.sz - 1;
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        vec[num] += cur;
        if (num) {
            if (q.empty() || q.front() != cur) {
                while (vec.sz > num) {
                    q.push(vec.back());
                    vec.pop_back();
                }
            }
        }
        if (num == 0) {
            num = vec.sz - 1;
        }
        else {
            num--;
        }
    }

    for (auto i : vec) {
        cout << i;
    }
    for (int i = nn - k + 2; i <= nn; i++) {
        cout << ans[i];
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
}

/*
4
3 3 0 0 0 0 0 5 3
 */

Compilation message (stderr)

devil.cpp: In function 'void solve()':
devil.cpp:77:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |                 while (vec.sz > num) {
      |                        ~~~~~~~^~~~~

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