oj.uz

Submission #199418

# Submission time Handle Problem Language Result Execution time Memory
199418 2020-02-01T10:43:42 Z popovicirobert Devil's Share (RMI19_devil) C++14
100 / 100
 118 ms 4432 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;



int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int t, i, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> t;

    while(t--) {
        cin >> k;

        vector <int> num(10);
        for(i = 1; i <= 9; i++) {
            cin >> num[i];
        }

        string b;
        int cur = 0;
        for(i = 9; i >= 1; i--) {
            while(num[i] > 0 && cur < k - 1) {
                cur++;
                b.push_back(i + '0');
                num[i]--;
            }
        }
        reverse(b.begin(), b.end());

        vector <string> a;
        for(i = 9; i >= 1; i--) {
            if(num[i]) {
                a.resize(num[i], string(1, i + '0'));
                num[i] = 0;
                break;
            }
        }

        deque <string> deq;
        for(i = 1; i <= 9; i++) {
            while(num[i] > 0) {
                num[i]--;
                deq.push_back(string(1, i + '0'));
            }
        }

        int pos = (int)a.size() - 1;
        while(deq.size()) {
            auto cur = deq.front();
            deq.pop_front();

            a[pos].append(cur);

            if((deq.empty() || deq.front() != cur) && pos != 0) {
                while(a.size() > pos) {
                    deq.push_back(a.back());
                    a.pop_back();
                }
            }

            pos = (pos == 0 ? a.size() : pos) - 1;
        }

        for(auto it : a) {
            cout << it;
        }
        cout << b << "\n";
    }

    return 0;
}

Compilation message

devil.cpp: In function 'int main()':
devil.cpp:67:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(a.size() > pos) {
                       ~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1400 KB Output is correct
2 Correct 99 ms 1316 KB Output is correct
3 Correct 97 ms 1400 KB Output is correct
4 Correct 118 ms 1400 KB Output is correct
5 Correct 67 ms 1272 KB Output is correct
6 Correct 61 ms 1400 KB Output is correct
7 Correct 53 ms 1400 KB Output is correct
8 Correct 56 ms 1616 KB Output is correct
9 Correct 61 ms 4364 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1272 KB Output is correct
2 Correct 57 ms 1528 KB Output is correct
3 Correct 39 ms 3708 KB Output is correct
4 Correct 65 ms 3932 KB Output is correct
5 Correct 107 ms 4432 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 106 ms 1400 KB Output is correct
3 Correct 99 ms 1316 KB Output is correct
4 Correct 97 ms 1400 KB Output is correct
5 Correct 118 ms 1400 KB Output is correct
6 Correct 67 ms 1272 KB Output is correct
7 Correct 61 ms 1400 KB Output is correct
8 Correct 53 ms 1400 KB Output is correct
9 Correct 56 ms 1616 KB Output is correct
10 Correct 61 ms 4364 KB Output is correct
11 Correct 67 ms 1272 KB Output is correct
12 Correct 57 ms 1528 KB Output is correct
13 Correct 39 ms 3708 KB Output is correct
14 Correct 65 ms 3932 KB Output is correct
15 Correct 107 ms 4432 KB Output is correct
16 Correct 89 ms 2040 KB Output is correct
17 Correct 95 ms 2300 KB Output is correct
18 Correct 87 ms 1912 KB Output is correct
19 Correct 115 ms 2680 KB Output is correct
20 Correct 38 ms 1404 KB Output is correct
21 Correct 37 ms 1400 KB Output is correct
22 Correct 37 ms 1592 KB Output is correct
23 Correct 61 ms 4352 KB Output is correct