This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000 + 7;
const int M = 15000 + 1;
int n, m, a[M], b[M];
int vertical[M];
struct MyBitset {
vector<ll> b;
int n;
void resize(int nn) {
n = nn;
b.resize(n / 63 + 2, 0);
}
void set(int x) {
b[x / 63] |= (1LL << (x % 63));
}
bool get(int x) {
if (x > n) {
return 0;
}
if (b[x / 63] & (1LL << (x % 63))) {
return true;
} else {
return false;
}
}
};
int f[M];
void add(int i, int x) {
for (; i <= n; i += i & -i) f[i] += x;
}
int get(int i) {
int res = 0;
for (; i >= 1; i -= i & -i) res += f[i];
return res;
}
int get_next(int x) {
int l = 1, r = x, sol = 0;
while (l <= r) {
int m = (l + r) / 2;
if (get(x) - get(m - 1) >= 1) {
l = m + 1;
sol = m;
} else {
r = m - 1;
}
}
return sol;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; ++i) cin >> b[i];
int sumA = 0;
for (int i = 1; i <= n; ++i) {
sumA += a[i];
}
reverse(b + 1, b + m + 1);
for (int i = 1; i <= sumA; ++i) {
for (int j = 1; j <= n; ++j) {
vertical[i] += min(i, a[j]);
}
}
vector<bitset<M>> dp(M + 1);
bitset<M> full;
for (int i = 0; i < M; ++i) full[i] = 1;
dp[0][0] = 1;
for (int i = 1; i <= m; ++i) {
for (int c = 1; c <= (M - 1) / b[i]; ++c) {
dp[c] |= (dp[c - 1] << b[i]);
dp[c] &= full >> max(0, M - 1 - vertical[c]);
}
}
for (int x = 1; x <= sumA; ++x) {
if (dp[x][sumA] == 1) {
cout << x << "\n";
vector<pair<int, int>> boxes;
int cnt = x;
int sum = sumA;
int pos = m;
while (pos > 0) {
while (cnt > 0 && dp[cnt - 1][sumA - b[pos]]) {
sumA -= b[pos];
cnt--;
boxes.push_back({b[pos], boxes.size()});
}
pos--;
}
vector<vector<int>> sol(boxes.size());
vector<vector<int>> occ(n + 1);
sort(boxes.rbegin(), boxes.rend());
for (int i = 0; i < boxes.size(); ++i) {
occ[boxes[i].first].push_back(boxes[i].second);
add(boxes[i].first, 1);
}
for (int it = 1; it <= n; ++it) {
vector<int> mod;
int x = get_next(n);
int val = a[it];
while (a[it] > 0) {
int steps = min(a[it], (int) occ[x].size());
for (int i = 1; i <= steps; ++i) {
mod.push_back(x);
}
a[it] -= steps;
x = get_next(x - 1);
}
reverse(mod.begin(), mod.end());
for (auto i : mod) {
assert(occ[i].size() > 0);
int x = occ[i].back();
occ[i].pop_back();
add(i, -1);
sol[x].push_back(it);
if (i >= 2) {
add(i - 1, 1);
occ[i - 1].push_back(x);
}
}
}
for (int i = 0; i < boxes.size(); ++i) {
cout << sol[i].size() << " ";
for (auto j : sol[i]) {
cout << j << " ";
}
cout << "\n";
}
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Compilation message (stderr)
cookies.cpp: In function 'int main()':
cookies.cpp:112:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0; i < boxes.size(); ++i) {
| ~~^~~~~~~~~~~~~~
cookies.cpp:119:21: warning: unused variable 'val' [-Wunused-variable]
119 | int val = a[it];
| ^~~
cookies.cpp:145:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i = 0; i < boxes.size(); ++i) {
| ~~^~~~~~~~~~~~~~
cookies.cpp:98:17: warning: unused variable 'sum' [-Wunused-variable]
98 | int sum = sumA;
| ^~~
# | 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... |