#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
#include <algorithm>
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> solve(std::vector<int> &a) {
if(a[0] == a.back()) return a;
//for(auto x : a) std::cout << x << ' ';
//std::cout << std::endl;
int sz = 0;
int mx = a.back();
while(a.back() == mx) {
sz++;
a.pop_back();
}
std::vector<std::vector<int>> b;
std::vector<int> wtf(sz, 0), cur(1, mx);
int pt = 0, c = 0;
std::reverse(a.begin(), a.end());
while(!a.empty()) {
//std::cout << "entering while" << std::endl;
for(int l = pt, r = pt; l < sz; l = r) {
if(a.empty()) {
break;
}
int got = a.back();
while(r < sz && !a.empty() && a.back() == got) {
r++;
a.pop_back();
}
if(r != sz) {
//std::cout << "pushing " << got << " to new" << std::endl;
for(int i = l; i < r; i++) {
wtf[i] = c;
}
c++;
b.push_back(cur);
b.back().push_back(got);
pt = r;
} else {
//std::cout << "pushing " << got << " to cur" << std::endl;
cur.push_back(got);
}
}
}
//std::cout << "c is " << c << ", pt is " << pt << std::endl;
for(int i = pt; i < sz; i++) {
wtf[i] = c;
}
c++;
b.push_back(cur);
cur.clear();
//for(auto x : wtf) std::cout << x << ' ';
//std::cout << std::endl;
auto ha = solve(wtf);
std::vector<int> ans;
for(auto id : ha) {
//std::cout << "getting id " << id << std::endl;
for(auto x : b[id]) {
ans.push_back(x);
}
}
//for(auto x : ans) std::cout << x << ' ';
//std::cout << std::endl;
return ans;
}
void solve() {
int k;
std::vector<int> a;
std::cin >> k;
for(int i = 1; i <= 9; i++) {
int x;
std::cin >> x;
while(x--) {
a.push_back(i);
}
}
std::string end;
for(int i = 1; i < k; i++) {
end += char('0' + a.back());
a.pop_back();
}
a = solve(a);
for(auto x : a) std::cout << x;
std::reverse(end.begin(), end.end());
std::cout << end << '\n';
}
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
int t;
std::cin >> t;
while(t--) {
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
1676 KB |
Output is correct |
2 |
Correct |
164 ms |
1784 KB |
Output is correct |
3 |
Correct |
143 ms |
1784 KB |
Output is correct |
4 |
Correct |
194 ms |
1784 KB |
Output is correct |
5 |
Correct |
73 ms |
1544 KB |
Output is correct |
6 |
Correct |
67 ms |
1400 KB |
Output is correct |
7 |
Correct |
64 ms |
1400 KB |
Output is correct |
8 |
Correct |
62 ms |
1648 KB |
Output is correct |
9 |
Correct |
62 ms |
3196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
121 ms |
1656 KB |
Output is correct |
2 |
Correct |
84 ms |
1784 KB |
Output is correct |
3 |
Correct |
39 ms |
2396 KB |
Output is correct |
4 |
Correct |
70 ms |
11332 KB |
Output is correct |
5 |
Correct |
134 ms |
21292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
189 ms |
1676 KB |
Output is correct |
3 |
Correct |
164 ms |
1784 KB |
Output is correct |
4 |
Correct |
143 ms |
1784 KB |
Output is correct |
5 |
Correct |
194 ms |
1784 KB |
Output is correct |
6 |
Correct |
73 ms |
1544 KB |
Output is correct |
7 |
Correct |
67 ms |
1400 KB |
Output is correct |
8 |
Correct |
64 ms |
1400 KB |
Output is correct |
9 |
Correct |
62 ms |
1648 KB |
Output is correct |
10 |
Correct |
62 ms |
3196 KB |
Output is correct |
11 |
Correct |
121 ms |
1656 KB |
Output is correct |
12 |
Correct |
84 ms |
1784 KB |
Output is correct |
13 |
Correct |
39 ms |
2396 KB |
Output is correct |
14 |
Correct |
70 ms |
11332 KB |
Output is correct |
15 |
Correct |
134 ms |
21292 KB |
Output is correct |
16 |
Correct |
133 ms |
2040 KB |
Output is correct |
17 |
Correct |
152 ms |
2296 KB |
Output is correct |
18 |
Correct |
126 ms |
1912 KB |
Output is correct |
19 |
Correct |
176 ms |
2808 KB |
Output is correct |
20 |
Correct |
46 ms |
1528 KB |
Output is correct |
21 |
Correct |
45 ms |
1400 KB |
Output is correct |
22 |
Correct |
40 ms |
1488 KB |
Output is correct |
23 |
Correct |
54 ms |
2884 KB |
Output is correct |