Submission #237412

#	Time	Username	Problem	Language	Result	Execution time	Memory
237412		Leonardo_Paes	Devil's Share (RMI19_devil)	C++17	100 / 100	129 ms	5972 KiB

devil

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int freq[15];

struct comp{
    bool operator () (const string &a, const string &b){
        if(a.size() == b.size()) return a < b;
        return a.size() > b.size();
    }
};

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int t;

    cin >> t;

    while(t--){
        int k, n = 0;

        cin >> k;

        for(int i=1; i<=9; i++) cin >> freq[i], n += freq[i];

        deque<string> s;

        string rest;

        int aux = n;

        for(int i=1; i<=9; i++){
            for(int j=1; j<=freq[i]; j++){
                if(aux>=k)s.push_back(string(1, i + '0'));
                else rest += i + '0';
                aux--;
            }
        }

        deque<string> fila;

        int pos;

        for(int i = n - k; i>=0; i--){
            pos = i;
            fila.push_back(s[i]);
            if(i == 0 or s[i] != s[i-1]) break;
        }

        swap(fila, s);

        int idpos = s.size() - 1;

        while(fila.size() > pos) fila.pop_back();

        while(!fila.empty()){
            string u = fila.front();

            fila.pop_front();

            s[idpos] += u;

            if((fila.empty() or u != fila.front()) and idpos){
                while(idpos < (int)s.size()){
                    fila.push_back(s.back());
                    s.pop_back();
                }
            }

            if(!idpos) idpos = s.size();

            idpos--;
        }

        string ans;

        for(auto q : s) ans += q;

        cout << ans + rest << "\n";
    }

    return 0;
}

Compilation message (stderr)

devil.cpp: In function 'int main()':
devil.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(fila.size() > pos) fila.pop_back();
               ~~~~~~~~~~~~^~~~~
devil.cpp:46:13: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int pos;
             ^~~

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