#include <bits/stdc++.h>
using namespace std;
using Test = pair <vector <int>, int>; // (freq, K)
void ReadTest(Test &t) {
int& K = t.second;
cin >> K;
vector <int>& v = t.first;
v.resize(10);
for (int i = 1; i < 10; ++i) {
cin >> v[i];
}
}
namespace CataFrancu {
#define NIL -1
struct list {
int next; /* index of the next digit in this chain */
int end; /* index of the last digit in this chain */
char digit; /* 0-9 */
char distinct; /* this list is different from the one to its left */
};
/* print lists in the [from, to) range, limited to max digits */
void print_lists(stringstream &ss, const vector<list>& l, const vector<int>& counts, int from, int to, int max) {
for (int i = from; i < to; i++) {
int pos = i;
while (pos != NIL) {
if (max) {
ss << (char)('0' + l[pos].digit);
max--;
}
pos = l[pos].next;
}
}
}
string Solve(Test t) {
vector <int>& counts = t.first;
int& k = t.second;
int n = 0, c, i, j;
for (int i = 1; i < 10; ++i) {
n += counts[i];
}
vector <list> l(n);
/* initialize N single-digit chains */
c = 0;
for (i = 0; i < n; i++) {
while (!counts[c]) {
c++;
}
l[i].next = NIL;
l[i].end = i;
l[i].digit = c;
l[i].distinct = (!i || (l[i].digit != l[i - 1].digit));
counts[c]--;
}
/* starting index of the rightmost run of identical chains */
/* (we know the ending index is n - k) */
int jstart = n - k;
while (jstart && (l[jstart - 1].digit == l[n - k].digit)) {
jstart--;
}
/* Distribute lists, starting from the left, in round robin fashion, into
the run of identical chains to the right. In time, the run will shrink
towards the right. Stop when there are no more elements to distribute to
the left of the run. */
i = 0; /* list currently being distributed */
j = jstart; /* list currently being appended to */
while (i < jstart || j > jstart) { /* stop when i, j and jstart coincide */
/* append l[i] to l[j] */
l[l[j].end].next = i;
l[j].end = l[i].end;
/* shrink the run if l[i] is distinct from the one before it */
if (l[i].distinct) {
l[j].distinct = 1;
jstart = j;
}
i++;
j++;
if (j > n - k) {
j = jstart;
}
}
/* the devil's due is the chain at position n - k, possibly padded to
length k with larger digits */
stringstream ss;
//print_lists(ss, l, counts, n - k, n, k); /* print the devil's due */
print_lists(ss, l, counts, jstart, n, n); /* print the complete permutation */
return ss.str();
}
void SolveCataFrancu() {
int T;
cin >> T;
while (T--) {
Test t;
ReadTest(t);
cout << Solve(t) << '\n';
}
}
}
int main() {
CataFrancu::SolveCataFrancu();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
261 ms |
1272 KB |
Output is correct |
2 |
Correct |
191 ms |
1784 KB |
Output is correct |
3 |
Correct |
163 ms |
1784 KB |
Output is correct |
4 |
Correct |
294 ms |
2168 KB |
Output is correct |
5 |
Correct |
42 ms |
1400 KB |
Output is correct |
6 |
Correct |
43 ms |
1272 KB |
Output is correct |
7 |
Correct |
43 ms |
1272 KB |
Output is correct |
8 |
Correct |
39 ms |
1448 KB |
Output is correct |
9 |
Correct |
37 ms |
2836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
1272 KB |
Output is correct |
2 |
Correct |
101 ms |
1528 KB |
Output is correct |
3 |
Correct |
38 ms |
2796 KB |
Output is correct |
4 |
Correct |
43 ms |
2936 KB |
Output is correct |
5 |
Correct |
50 ms |
2968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
384 KB |
Output is correct |
2 |
Correct |
261 ms |
1272 KB |
Output is correct |
3 |
Correct |
191 ms |
1784 KB |
Output is correct |
4 |
Correct |
163 ms |
1784 KB |
Output is correct |
5 |
Correct |
294 ms |
2168 KB |
Output is correct |
6 |
Correct |
42 ms |
1400 KB |
Output is correct |
7 |
Correct |
43 ms |
1272 KB |
Output is correct |
8 |
Correct |
43 ms |
1272 KB |
Output is correct |
9 |
Correct |
39 ms |
1448 KB |
Output is correct |
10 |
Correct |
37 ms |
2836 KB |
Output is correct |
11 |
Correct |
201 ms |
1272 KB |
Output is correct |
12 |
Correct |
101 ms |
1528 KB |
Output is correct |
13 |
Correct |
38 ms |
2796 KB |
Output is correct |
14 |
Correct |
43 ms |
2936 KB |
Output is correct |
15 |
Correct |
50 ms |
2968 KB |
Output is correct |
16 |
Correct |
323 ms |
2040 KB |
Output is correct |
17 |
Correct |
315 ms |
2168 KB |
Output is correct |
18 |
Correct |
254 ms |
1912 KB |
Output is correct |
19 |
Correct |
440 ms |
2680 KB |
Output is correct |
20 |
Correct |
41 ms |
1272 KB |
Output is correct |
21 |
Correct |
44 ms |
1400 KB |
Output is correct |
22 |
Correct |
36 ms |
1456 KB |
Output is correct |
23 |
Correct |
41 ms |
2800 KB |
Output is correct |