oj.uz

Submission #685077

# Submission time Handle Problem Language Result Execution time Memory
685077 2023-01-23T09:33:05 Z nifeshe Devil's Share (RMI19_devil) C++17
100 / 100
 78 ms 4912 KB 
#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

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

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2040 KB Output is correct
2 Correct 59 ms 1700 KB Output is correct
3 Correct 70 ms 1776 KB Output is correct
4 Correct 72 ms 2124 KB Output is correct
5 Correct 54 ms 1452 KB Output is correct
6 Correct 61 ms 1420 KB Output is correct
7 Correct 38 ms 1396 KB Output is correct
8 Correct 36 ms 1688 KB Output is correct
9 Correct 40 ms 4456 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1796 KB Output is correct
2 Correct 40 ms 1484 KB Output is correct
3 Correct 25 ms 4584 KB Output is correct
4 Correct 38 ms 4912 KB Output is correct
5 Correct 66 ms 4712 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 67 ms 2040 KB Output is correct
3 Correct 59 ms 1700 KB Output is correct
4 Correct 70 ms 1776 KB Output is correct
5 Correct 72 ms 2124 KB Output is correct
6 Correct 54 ms 1452 KB Output is correct
7 Correct 61 ms 1420 KB Output is correct
8 Correct 38 ms 1396 KB Output is correct
9 Correct 36 ms 1688 KB Output is correct
10 Correct 40 ms 4456 KB Output is correct
11 Correct 43 ms 1796 KB Output is correct
12 Correct 40 ms 1484 KB Output is correct
13 Correct 25 ms 4584 KB Output is correct
14 Correct 38 ms 4912 KB Output is correct
15 Correct 66 ms 4712 KB Output is correct
16 Correct 64 ms 2024 KB Output is correct
17 Correct 58 ms 2164 KB Output is correct
18 Correct 52 ms 1992 KB Output is correct
19 Correct 78 ms 2640 KB Output is correct
20 Correct 25 ms 1364 KB Output is correct
21 Correct 24 ms 1400 KB Output is correct
22 Correct 24 ms 1608 KB Output is correct
23 Correct 36 ms 4628 KB Output is correct