oj.uz

Submission #685093

# Submission time Handle Problem Language Result Execution time Memory
685093 2023-01-23T10:48:51 Z vovamr Devil's Share (RMI19_devil) C++17
100 / 100
 284 ms 6924 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int k;
	cin >> k;
	ve<int> c(10);
	for (int i = 1; i < 10; ++i) cin >> c[i];

	ve<int> last; int kk = k - 1;
	for (int i = 9; ~i; --i) {
		while (kk && c[i]) {
			last.pb(i);
			--kk, --c[i];
		}
	}
	reverse(all(last));

	int mx = -1;
	for (int i = 9; ~i; --i) {
		if (c[i]) {
			mx = i;
			break;
		}
	}
	if (!mx) {
		for (auto &i : last) cout << i;
		cout << '\n';
		return;
	}

	ve<ve<int>> answer(c[mx]);
	for (auto &vec : answer) vec = {mx};
	
	c[mx] = 0;
	
	queue<ve<int>> q;
	for (int i = 0; i < 10; ++i) {
		while (c[i]--) {
			q.push(ve<int>{i});
		}
	}

	int ptr = sz(answer) - 1;
	while (sz(q)) {
		ve<int> cc = q.front();
		q.pop();
		for (const auto &x : cc) answer[ptr].pb(x);

		if (ptr && (!sz(q) || q.front() != cc)) {
			while (sz(answer) > ptr) {
				q.push(answer.back());
				answer.pop_back();
			}
		}
		ptr = (!ptr ? sz(answer) - 1 : ptr - 1);
	}
	for (auto &vec : answer) {
		for (auto &x : vec) cout << x;
	}
	for (auto &x : last) cout << x;
	cout << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

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 143 ms 1300 KB Output is correct
2 Correct 136 ms 1240 KB Output is correct
3 Correct 140 ms 1356 KB Output is correct
4 Correct 142 ms 1336 KB Output is correct
5 Correct 159 ms 1624 KB Output is correct
6 Correct 139 ms 1500 KB Output is correct
7 Correct 124 ms 1520 KB Output is correct
8 Correct 119 ms 2044 KB Output is correct
9 Correct 115 ms 6684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1176 KB Output is correct
2 Correct 104 ms 1348 KB Output is correct
3 Correct 88 ms 5972 KB Output is correct
4 Correct 193 ms 6732 KB Output is correct
5 Correct 284 ms 6864 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 143 ms 1300 KB Output is correct
3 Correct 136 ms 1240 KB Output is correct
4 Correct 140 ms 1356 KB Output is correct
5 Correct 142 ms 1336 KB Output is correct
6 Correct 159 ms 1624 KB Output is correct
7 Correct 139 ms 1500 KB Output is correct
8 Correct 124 ms 1520 KB Output is correct
9 Correct 119 ms 2044 KB Output is correct
10 Correct 115 ms 6684 KB Output is correct
11 Correct 92 ms 1176 KB Output is correct
12 Correct 104 ms 1348 KB Output is correct
13 Correct 88 ms 5972 KB Output is correct
14 Correct 193 ms 6732 KB Output is correct
15 Correct 284 ms 6864 KB Output is correct
16 Correct 104 ms 1100 KB Output is correct
17 Correct 113 ms 1212 KB Output is correct
18 Correct 99 ms 1124 KB Output is correct
19 Correct 140 ms 1392 KB Output is correct
20 Correct 89 ms 1372 KB Output is correct
21 Correct 86 ms 1312 KB Output is correct
22 Correct 85 ms 1888 KB Output is correct
23 Correct 116 ms 6924 KB Output is correct