QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241486 | #6339. Cookies | Leasier | 12 | 9ms | 58856kb | C++98 | 2.0kb | 2023-11-06 08:43:56 | 2023-11-06 08:43:56 |
Judging History
answer
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
int a[15007], suf[15007], val[15007], b[15007], ansc[15007];
pair<int, int> save[15007];
priority_queue<pair<int, int> > q;
bitset<15007> temp, bs[15007];
vector<bitset<15007> > v[15007];
int main(){
int n, max_val = 0, sum = 0, m, ansx = -1;
cin >> n;
for (register int i = 1; i <= n; i++){
cin >> a[i];
suf[a[i]]++;
max_val = max(max_val, a[i]);
sum += a[i];
}
for (register int i = max_val; i >= 1; i--){
suf[i] += suf[i + 1];
}
for (register int i = 1; i <= max_val; i++){
val[i] = val[i - 1] + suf[i];
}
for (register int i = max_val + 1; i <= sum; i++){
val[i] = sum;
}
bs[0][0] = true;
for (register int i = 1; i <= sum; i++){
bs[i] = bs[i - 1];
for (register int j = val[i - 1] + 1; j <= val[i]; j++){
bs[i][j] = true;
}
}
cin >> m;
for (register int i = 1; i <= m; i++){
cin >> b[i];
}
v[m + 1].resize(1);
v[m + 1][0][0] = true;
for (register int i = m; i >= 1; i--){
int size = v[i + 1].size();
v[i].resize(sum / b[i] + 1);
for (register int j = 0; b[i] * j <= sum; j++){
if (j < size) v[i][j] = v[i + 1][j];
if (j > 0){
temp = v[i][j - 1];
temp <<= b[i];
v[i][j] |= temp;
}
v[i][j] &= bs[j];
}
}
for (register int i = 0; i <= sum; i++){
if (v[1][i][sum]){
ansx = i;
break;
}
}
if (ansx == -1){
cout << -1;
return 0;
}
cout << ansx << endl;
for (register int i = ansx, j = sum, k = 1; i >= 1; i--, j -= b[k]){
while (!v[k][i][j] || !v[k][i - 1][j - b[k]]) k++;
ansc[i] = b[k];
}
for (register int i = 1; i <= n; i++){
q.push(make_pair(a[i], i));
}
for (register int i = 1; i <= ansx; i++){
cout << ansc[i] << " ";
for (register int j = 1; j <= ansc[i]; j++){
save[j] = q.top();
q.pop();
cout << save[j].second << " ";
}
cout << endl;
for (register int j = 1; j <= ansc[i]; j++){
if (--save[j].first > 0) q.push(save[j]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 6
Accepted
time: 0ms
memory: 31684kb
input:
1 1 1 1
output:
1 1 1
result:
ok good!
Test #2:
score: 0
Accepted
time: 6ms
memory: 31608kb
input:
2 1 1 1 1
output:
2 1 2 1 1
result:
ok good!
Test #3:
score: 0
Accepted
time: 6ms
memory: 31424kb
input:
2 1 1 1 2
output:
1 2 2 1
result:
ok good!
Test #4:
score: 0
Accepted
time: 0ms
memory: 31432kb
input:
2 1 1 2 1 2
output:
1 2 2 1
result:
ok good!
Test #5:
score: 0
Accepted
time: 0ms
memory: 31432kb
input:
4 1 1 1 1 2 2 3
output:
2 2 4 3 2 2 1
result:
ok good!
Test #6:
score: 0
Accepted
time: 6ms
memory: 31448kb
input:
8 1 1 1 1 1 1 1 1 3 1 4 5
output:
2 4 8 7 6 5 4 4 3 2 1
result:
ok good!
Test #7:
score: 0
Accepted
time: 0ms
memory: 31960kb
input:
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 ...
output:
500 1 500 1 499 1 498 1 497 1 496 1 495 1 494 1 493 1 492 1 491 1 490 1 489 1 488 1 487 1 486 1 485 1 484 1 483 1 482 1 481 1 480 1 479 1 478 1 477 1 476 1 475 1 474 1 473 1 472 1 471 1 470 1 469 1 468 1 467 1 466 1 465 1 464 1 463 1 462 1 461 1 460 1 459 1 ...
result:
ok good!
Test #8:
score: 0
Accepted
time: 6ms
memory: 31432kb
input:
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 ...
output:
1 500 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 42...
result:
ok good!
Test #9:
score: 0
Accepted
time: 0ms
memory: 38044kb
input:
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 ...
output:
2 499 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 42...
result:
ok good!
Test #10:
score: -6
Runtime Error
input:
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 ...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #28:
score: 7
Accepted
time: 3ms
memory: 31476kb
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: 0
Accepted
time: 0ms
memory: 32140kb
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...
result:
ok good!
Test #30:
score: 0
Accepted
time: 9ms
memory: 36676kb
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 ...
result:
ok good!
Test #31:
score: 0
Accepted
time: 8ms
memory: 58856kb
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 ...
result:
ok good!
Test #32:
score: 0
Accepted
time: 3ms
memory: 31440kb
input:
2 2 1 1 1
output:
3 1 1 1 2 1 1
result:
ok good!
Test #33:
score: 0
Accepted
time: 0ms
memory: 31512kb
input:
2 1 2 1 2
output:
-1
result:
ok no solution
Test #34:
score: 0
Accepted
time: 0ms
memory: 31432kb
input:
3 1 2 3 1 2
output:
3 2 3 2 2 3 2 2 3 1
result:
ok good!
Test #35:
score: -7
Runtime Error
input:
3 3 2 1 1 3
output:
3
result:
Subtask #3:
score: 12
Accepted
Test #45:
score: 12
Accepted
time: 0ms
memory: 31532kb
input:
2 7 8 2 1 2
output:
8 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2
result:
ok good!
Test #46:
score: 0
Accepted
time: 0ms
memory: 31452kb
input:
3 5 4 6 2 2 3
output:
6 3 3 1 2 3 3 1 2 3 3 1 2 2 3 1 2 3 2 2 3 1
result:
ok good!
Test #47:
score: 0
Accepted
time: 0ms
memory: 31492kb
input:
3 4 2 9 3 1 2 3
output:
9 3 3 1 2 3 3 1 2 2 3 1 2 3 1 1 3 1 3 1 3 1 3 1 3
result:
ok good!
Test #48:
score: 0
Accepted
time: 0ms
memory: 31512kb
input:
4 3 5 4 3 2 3 4
output:
5 3 2 3 4 3 2 3 1 3 2 4 3 3 2 1 4 3 3 2 1
result:
ok good!
Test #49:
score: 0
Accepted
time: 3ms
memory: 31560kb
input:
4 1 4 5 5 3 1 3 4
output:
5 3 4 3 2 3 4 3 2 3 4 3 2 3 4 3 2 3 4 3 1
result:
ok good!
Test #50:
score: 0
Accepted
time: 0ms
memory: 31460kb
input:
4 3 3 6 3 3 2 3 4
output:
6 4 3 4 2 1 3 3 4 2 2 3 1 2 3 4 2 3 2 2 3 1
result:
ok good!
Test #51:
score: 0
Accepted
time: 0ms
memory: 31516kb
input:
5 4 3 3 3 1 3 2 4 5
output:
4 4 1 4 3 2 4 1 4 3 2 4 1 5 4 3 2 2 1
result:
ok good!
Test #52:
score: 0
Accepted
time: 0ms
memory: 31472kb
input:
5 4 3 3 3 2 3 3 4 5
output:
4 5 1 4 3 2 5 4 1 4 3 2 3 1 5 4 3 3 2 1
result:
ok good!
Test #53:
score: 0
Accepted
time: 0ms
memory: 31448kb
input:
5 4 4 4 2 1 3 2 4 5
output:
5 5 3 2 1 4 5 4 3 2 1 4 2 3 2 2 1 3 2 2 1
result:
ok good!
Test #54:
score: 0
Accepted
time: 3ms
memory: 31472kb
input:
5 3 3 3 3 3 3 1 2 4
output:
5 4 5 4 3 2 4 1 5 4 3 4 2 1 5 4 2 3 2 1 1
result:
ok good!
Test #55:
score: 0
Accepted
time: 0ms
memory: 31676kb
input:
6 3 3 3 2 2 2 3 2 4 6
output:
-1
result:
ok no solution
Test #56:
score: 0
Accepted
time: 3ms
memory: 31512kb
input:
6 3 3 3 2 2 2 3 2 5 6
output:
3 5 3 2 1 6 5 5 4 3 2 1 6 5 5 4 3 2 1
result:
ok good!
Test #57:
score: 0
Accepted
time: 3ms
memory: 31584kb
input:
6 4 4 3 2 1 1 3 1 3 5
output:
5 5 2 1 3 4 6 5 2 1 3 5 4 3 2 1 3 1 2 1 1
result:
ok good!
Test #58:
score: 0
Accepted
time: 0ms
memory: 31496kb
input:
6 7 2 2 2 1 1 5 2 3 4 5 6
output:
7 3 1 4 3 2 1 2 2 1 6 2 1 5 2 1 4 2 1 3 2 2 1
result:
ok good!
Test #59:
score: 0
Accepted
time: 0ms
memory: 31676kb
input:
7 3 3 3 2 2 1 1 3 1 4 6
output:
4 6 3 2 1 5 4 7 4 3 2 1 6 4 5 4 3 2 1 1
result:
ok good!
Test #60:
score: 0
Accepted
time: 0ms
memory: 31464kb
input:
7 4 4 3 1 1 1 1 3 1 4 6
output:
6 4 2 1 3 7 4 2 1 3 6 4 2 1 5 4 1 3 1 2 1 1
result:
ok good!
Test #61:
score: 0
Accepted
time: 5ms
memory: 31464kb
input:
8 2 2 2 2 2 2 2 1 6 1 2 3 4 6 7
output:
3 7 7 6 5 4 3 2 1 7 8 7 6 5 4 3 2 1 1
result:
ok good!
Test #62:
score: 0
Accepted
time: 3ms
memory: 31440kb
input:
8 3 3 3 2 1 1 1 1 4 4 6 7 8
output:
3 7 3 2 1 4 8 7 6 4 3 2 1 5 4 4 3 2 1
result:
ok good!
Test #63:
score: 0
Accepted
time: 0ms
memory: 31476kb
input:
8 4 3 3 1 1 1 1 1 4 1 6 7 8
output:
8 8 1 3 2 8 7 6 5 4 1 1 1 3 1 2 1 1 1 3 1 2 1 1
result:
ok good!
Test #64:
score: 0
Accepted
time: 0ms
memory: 31456kb
input:
9 4 3 2 1 1 1 1 1 1 4 3 4 5 7
output:
4 5 1 2 3 9 8 4 1 2 7 6 3 1 5 4 3 3 2 1
result:
ok good!
Test #65:
score: 0
Accepted
time: 0ms
memory: 31492kb
input:
12 3 2 1 1 1 1 1 1 1 1 1 1 9 1 4 5 6 7 8 9 10 11
output:
3 10 1 2 12 11 10 9 8 7 6 5 4 1 4 3 2 1 1
result:
ok good!
Test #66:
score: 0
Accepted
time: 0ms
memory: 31648kb
input:
14 2 1 1 1 1 1 1 1 1 1 1 1 1 1 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14
output:
2 14 1 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1
result:
ok good!
Test #67:
score: 0
Accepted
time: 0ms
memory: 31508kb
input:
4 2 2 2 1 2 1 4
output:
4 4 3 2 1 4 1 3 1 2 1 1
result:
ok good!
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%