QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525908 | #6339. Cookies | Qwerty1232# | 0 | 335ms | 883488kb | C++23 | 4.7kb | 2024-08-21 03:05:10 | 2024-08-21 03:05:11 |
Judging History
answer
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
// constexpr int N = 1.5e4 + 5;
void chmin(auto& a, auto b) {
a = std::min(a, b);
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> input(n);
for (auto& i : input) {
std::cin >> i;
}
int m;
std::cin >> m;
std::vector<int> sz(m);
for (auto& i : sz) {
std::cin >> i;
}
int mx = std::max_element(input.begin(), input.end()).operator*();
int sm = std::accumulate(input.begin(), input.end(), 0);
std::vector<int> shit(input.begin(), input.end());
std::sort(shit.rbegin(), shit.rend());
std::vector<int> shit_suf(n + 1);
for (int i = n - 1, s = 0; i >= 0; i--) {
s += shit[i], shit_suf[i] = s;
}
std::vector<std::vector<std::vector<int>>> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = std::vector<std::vector<int>>(std::min<int>(mx, (sm / (i + 1))) + 1, std::vector<int>(shit_suf[i] + 1, sm + 5));
}
dp[n - 1][0][0] = 0;
for (int i = n - 1; i >= 0; i--) {
bool bx = std::binary_search(sz.begin(), sz.end(), i + 1);
if (bx) {
for (int j = 0; j + 1 < dp[i].size(); j++) {
for (int k = 0; k < dp[i][j].size(); k++) {
int k2 = k + 1;
if (k2 < dp[i][j + 1].size()) {
chmin(dp[i][j + 1][k2], dp[i][j][k] + 1);
}
}
}
}
if (i > 0) {
for (int j = 0; j < dp[i].size(); j++) {
for (int k = 0; k < dp[i][j].size(); k++) {
int k2 = k + j;
if (k2 < dp[i - 1][j].size()) {
chmin(dp[i - 1][j][k2], dp[i][j][k]);
}
}
}
}
}
std::vector<int> bx_sz;
{
std::array<int, 3> min = {sm + 1, -1, -1};
for (int k = 0; k < dp[0].size(); k++) {
if (sm < dp[0][k].size()) {
min = std::min(min, std::array<int, 3>{dp[0][k][sm], k, sm});
}
}
std::pair<int, int> pos(min[1], min[2]);
if (min.front() > sm || pos.first == -1) {
std::cout << "-1\n";
return 0;
}
for (int i = 0; i < n; i++) {
bool bx = std::binary_search(sz.begin(), sz.end(), i + 1);
if (bx) {
for (int j = (int)dp[i].size() - 1; j > 0; j--) {
for (int k = 0; k < dp[i][j].size(); k++) {
if (j != pos.first || k != pos.second) {
continue;
}
int k2 = k - 1;
if (0 <= k2 && k2 < dp[i][j - 1].size() && dp[i][j - 1][k2] + 1 == dp[i][j][k]) {
pos.first--, pos.second--;
bx_sz.push_back(i + 1);
}
}
}
}
if (i + 1 < n) {
for (int j = 0; j < dp[i].size(); j++) {
for (int k = 0; k < dp[i][j].size(); k++) {
if (j != pos.first || k != pos.second) {
continue;
}
int k2 = k - j;
if (0 <= k2 && k2 < dp[i + 1][j].size() && dp[i + 1][j][k2] == dp[i][j][k]) {
pos.second -= j;
}
}
}
}
}
}
// !
int q = bx_sz.size();
std::sort(bx_sz.rbegin(), bx_sz.rend());
std::priority_queue<std::pair<int, int>> heap;
for (int i = 0; i < n; i++) {
heap.push({input[i], i});
}
std::vector<std::vector<int>> ans(q);
for (int i = 0; i < q; i++) {
std::vector<std::pair<int, int>> vec(bx_sz[i]);
ans[i].resize(bx_sz[i]);
for (int j = 0; j < bx_sz[i]; j++) {
assert(heap.size());
vec[j] = heap.top(), heap.pop(), vec[j].first--, ans[i][j] = vec[j].second;
}
for (auto p : vec) {
if (p.first > 0) {
heap.push(p);
}
}
}
std::cout << ans.size() << "\n";
for (auto& vec : ans) {
std::cout << vec.size();
std::sort(vec.begin(), vec.end());
for (auto i : vec) {
std::cout << " " << i + 1;
}
std::cout << std::endl;
}
return 0;
}
/*
5 5 2 2 2 2 0
5 4 4 2 1 1 1
5 4 4 2 1 1 1
4 3 3 1 1 0 0
4 3 3 1 1 0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 3608kb
input:
1 1 1 1
output:
1 1 1
result:
ok good!
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3476kb
input:
2 1 1 1 1
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #2:
score: 0
Wrong Answer
Test #28:
score: 7
Accepted
time: 0ms
memory: 3628kb
input:
1 15 1 1
output:
15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok good!
Test #29:
score: 7
Accepted
time: 0ms
memory: 4628kb
input:
1 500 1 1
output:
500 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok good!
Test #30:
score: 7
Accepted
time: 11ms
memory: 38924kb
input:
1 3000 1 1
output:
3000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok good!
Test #31:
score: 7
Accepted
time: 335ms
memory: 883488kb
input:
1 15000 1 1
output:
15000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok good!
Test #32:
score: 0
Wrong Answer
time: 0ms
memory: 3828kb
input:
2 2 1 1 1
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #3:
score: 0
Wrong Answer
Test #45:
score: 12
Accepted
time: 0ms
memory: 3620kb
input:
2 7 8 2 1 2
output:
8 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2
result:
ok good!
Test #46:
score: 12
Accepted
time: 0ms
memory: 3628kb
input:
3 5 4 6 2 2 3
output:
6 3 1 2 3 3 1 2 3 3 1 2 3 2 1 3 2 2 3 2 1 3
result:
ok good!
Test #47:
score: 12
Accepted
time: 0ms
memory: 3832kb
input:
3 4 2 9 3 1 2 3
output:
9 3 1 2 3 3 1 2 3 2 1 3 2 1 3 1 3 1 3 1 3 1 3 1 3
result:
ok good!
Test #48:
score: 12
Accepted
time: 0ms
memory: 3824kb
input:
4 3 5 4 3 2 3 4
output:
5 3 2 3 4 3 1 2 3 3 2 3 4 3 1 2 4 3 1 2 3
result:
ok good!
Test #49:
score: 12
Accepted
time: 0ms
memory: 3560kb
input:
4 1 4 5 5 3 1 3 4
output:
5 3 2 3 4 3 2 3 4 3 2 3 4 3 2 3 4 3 1 3 4
result:
ok good!
Test #50:
score: 12
Accepted
time: 0ms
memory: 3536kb
input:
4 3 3 6 3 3 2 3 4
output:
6 4 1 2 3 4 3 2 3 4 2 1 3 2 3 4 2 2 3 2 1 3
result:
ok good!
Test #51:
score: 12
Accepted
time: 0ms
memory: 3608kb
input:
5 4 3 3 3 1 3 2 4 5
output:
4 4 1 2 3 4 4 1 2 3 4 4 1 3 4 5 2 1 2
result:
ok good!
Test #52:
score: 12
Accepted
time: 0ms
memory: 3608kb
input:
5 4 3 3 3 2 3 3 4 5
output:
4 5 1 2 3 4 5 4 1 2 3 4 3 1 4 5 3 1 2 3
result:
ok good!
Test #53:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
5 4 4 4 2 1 3 2 4 5
output:
-1
result:
wrong answer you didn't find a solution but jury did
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%