Submission #333399

#	Time	Username	Problem	Language	Result	Execution time	Memory
333399		keko37	Devil's Share (RMI19_devil)	C++14	100 / 100	183 ms	77624 KiB

devil

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 100005;

int t, k, cnt;
int br[15];
deque <char> dq[MAXN];
queue < vector <int> > q;
vector <int> v;

int spoji (int a, int b) {
    if (dq[a].size() >= dq[b].size()) {
        while (!dq[b].empty()) {
            dq[a].push_back(dq[b].front());
            dq[b].pop_front();
        }
        return a;
    } else {
        while (!dq[a].empty()) {
            dq[b].push_front(dq[a].back());
            dq[a].pop_back();
        }
        return b;
    }
}

void ispis () {
    for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        for (int j = 0; j < dq[ind].size(); j++) {
            cout << dq[ind][j];
        }
    }
    v.clear();
    for (int i = 1; i <= cnt; i++) dq[i].clear();
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> k;
        k--;
        for (int i = 1; i <= 9; i++) {
            cin >> br[i];
        }

        string suf = "";
        for (int i = 9; i >= 1; i--) {
            while (k > 0 && br[i] > 0) {
                k--; br[i]--;
                suf += (char) (i + '0');
            }
        }
        reverse(suf.begin(), suf.end());

        int mx = 0;
        for (int i = 1; i <= 9; i++) {
            if (br[i] > 0) mx = i;
        }

        cnt = 0;
        for (int i = 1; i <= 9; i++) {
            if (br[i] == 0) continue;
            vector <int> r;
            for (int j = 0; j < br[i]; j++) {
                cnt++;
                r.push_back(cnt);
                dq[cnt].push_back((char) (i + '0'));
            }
            if (i != mx) q.push(r); else v = r;
        }

        while (!q.empty()) {
            vector <int> r = q.front();
            q.pop();
            while (r.size() >= v.size()) {
                for (int i = 0; i < v.size(); i++) {
                    int b = r.back();
                    r.pop_back();
                    v[i] = spoji(v[i], b);
                }
            }
            if (r.empty()) continue;
            vector <int> res;
            while (!r.empty()) {
                int a = v.back(), b = r.back();
                v.pop_back(); r.pop_back();
                res.push_back(spoji(a, b));
            }
            q.push(res);
        }
        ispis();
        cout << suf << '\n';
    }
    return 0;
}

Compilation message (stderr)

devil.cpp: In function 'void ispis()':
devil.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
devil.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 0; j < dq[ind].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
devil.cpp: In function 'int main()':
devil.cpp:84:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for (int i = 0; i < v.size(); i++) {
      |                                 ~~^~~~~~~~~~

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