oj.uz

Submission #685084

# Submission time Handle Problem Language Result Execution time Memory
685084 2023-01-23T10:01:44 Z Bliznetc Devil's Share (RMI19_devil) C++17
100 / 100
 95 ms 6024 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1276 KB Output is correct
2 Correct 58 ms 1256 KB Output is correct
3 Correct 54 ms 1248 KB Output is correct
4 Correct 73 ms 1252 KB Output is correct
5 Correct 46 ms 1424 KB Output is correct
6 Correct 41 ms 1356 KB Output is correct
7 Correct 34 ms 1252 KB Output is correct
8 Correct 32 ms 1736 KB Output is correct
9 Correct 35 ms 4904 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1184 KB Output is correct
2 Correct 54 ms 1308 KB Output is correct
3 Correct 41 ms 6024 KB Output is correct
4 Correct 49 ms 5884 KB Output is correct
5 Correct 68 ms 5800 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 65 ms 1276 KB Output is correct
3 Correct 58 ms 1256 KB Output is correct
4 Correct 54 ms 1248 KB Output is correct
5 Correct 73 ms 1252 KB Output is correct
6 Correct 46 ms 1424 KB Output is correct
7 Correct 41 ms 1356 KB Output is correct
8 Correct 34 ms 1252 KB Output is correct
9 Correct 32 ms 1736 KB Output is correct
10 Correct 35 ms 4904 KB Output is correct
11 Correct 56 ms 1184 KB Output is correct
12 Correct 54 ms 1308 KB Output is correct
13 Correct 41 ms 6024 KB Output is correct
14 Correct 49 ms 5884 KB Output is correct
15 Correct 68 ms 5800 KB Output is correct
16 Correct 65 ms 1100 KB Output is correct
17 Correct 73 ms 1224 KB Output is correct
18 Correct 64 ms 1144 KB Output is correct
19 Correct 95 ms 1356 KB Output is correct
20 Correct 38 ms 1364 KB Output is correct
21 Correct 36 ms 1228 KB Output is correct
22 Correct 35 ms 1660 KB Output is correct
23 Correct 37 ms 5752 KB Output is correct