Submission #685077

#	Time	Username	Problem	Language	Result	Execution time	Memory
685077		nifeshe	Devil's Share (RMI19_devil)	C++17	100 / 100	78 ms	4912 KiB

devil

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 1e9 + 7;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e5 + 1;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

string check(int k, vector<int> cnt) {
    int n = accumulate(all(cnt), 0);
    string sf;
    int k0 = k;
    int pos = n - 1;
    while(k0 > 1) {
        for(int j = 9; ~j; j--) {
            if(cnt[j]) {
                sf.pb(char('0' + j));
                cnt[j]--;
                break;
            }
        }
        k0--;
        pos--;
    }
    reverse(all(sf));
    int lst = 10;
    while(!cnt[--lst]);
    vector<string> parts;
    parts.resize(cnt[lst], to_string(lst));
    cnt[lst] = 0;
    deque<string> q;
    for(int i = 0; i < 10; i++) {
        while(cnt[i]--) q.pb(to_string(i));
    }
    int p = sz(parts) - 1;
    while(sz(q)) {
//        for(int i = 0; i < sz(q); i++) cout << q[i] << ' ';
//        cout << endl;
        string curr = q.front(); q.pop_front();
        parts[p] += curr;
        if(p > 0) {
            if(q.empty() || q.front() != curr) {
                while(sz(parts) > p) {
                    q.pb(parts.back());
                    parts.pop_back();
                }
            }
        }
        if(!p) p = sz(parts) - 1;
        else p--;
    }
    string ans;
    for(auto s : parts) ans += s;
    ans += sf;
    return ans;
}

void solve() {
    int k;
    cin >> k;
    vector<int> cnt(10);
    for(int i = 1; i <= 9; i++) {
        cin >> cnt[i];
    }
    pair<int, string> best = {-inf, ""};
    auto get = [&](string &S) {
        int n = sz(S);
        int tmp = 0;
        for(int i = 0; i + k - 1 < n; i++) {
            umax(tmp, stoll(S.substr(i, k)));
        }
        return tmp;
    };
    string curr;
//    function<void(int)> rec = [&](int p) {
//        if(p == n) {
//            umax(best, {-get(curr), curr});
//            return;
//        }
//        for(int d = 1; d <= 9; d++) {
//            if(!cnt[d]) continue;
//            cnt[d]--;
//            curr.pb(char('0' + d));
//            rec(p + 1);
//            curr.pop_back();
//            cnt[d]++;
//        }
//    };
    cout << check(k, cnt) << '\n';
}

/*
62616236261623778899
62616236261623778899
623616236162361778899
623616236162361778899
*/

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

devil.cpp: In function 'void solve()':
devil.cpp:96:10: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   96 |     auto get = [&](string &S) {
      |          ^~~

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