This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// author: erray
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(37)
#endif
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
auto a = A;
sort(a.begin(), a.end());
int M;
cin >> M;
vector<int> B(M);
for (int i = 0; i < M; ++i) {
cin >> B[M - i - 1];
}
constexpr int SUM = 15000 + 1;
vector<int> allowed(SUM);
allowed[0] = -1;
{
int64_t sum = 0;
int p = 0;
for (int i = 1; i < SUM; ++i) {
while (p < N && a[p] < i) {
sum += a[p];
++p;
}
allowed[i] = sum + (N - p) * i;
}
}
using bs = bitset<SUM>;
bs one = ~bs{};
vector<bs> reach(SUM);
reach[0][0] = true;
for (auto add : B) {
for (int c = 1; c <= (SUM - 1) / add; ++c) {
reach[c] |= reach[c - 1] << add;
reach[c] &= one >> max(0, SUM - 1 - allowed[c]);
}
}
int size = 0;
int sum = accumulate(a.begin(), a.end(), 0);
while (size < SUM && !reach[size][sum]) ++size;
if (size == SUM) {
cout << -1 << '\n';
return 0;
}
debug(size);
vector<int> sizes;
reverse(B.begin(), B.end());
for (auto x : B) {
while (size > 0 && reach[size - 1][sum - x]) {
sum -= x;
size -= 1;
sizes.push_back(x);
}
}
//sort(sizes.rbegin(), sizes.rend());
reverse(sizes.begin(), sizes.end());
debug(sizes);
priority_queue<array<int, 2>> pq;
for (int i = 0; i < N; ++i) {
pq.push({A[i], i});
}
cout << int(sizes.size()) << '\n';
for (auto s : sizes) {
cout << s << ' ';
vector<array<int, 2>> temp;
for (int j = 0; j < s; ++j) {
auto t = pq.top(); pq.pop();
cout << t[1] + 1 << ' ';
temp.push_back(t);
}
cout << '\n';
for (auto t : temp) {
t[0] -= 1;
if (t[0] > 0) pq.push(t);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |