QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112669 | #6339. Cookies | Flamire | 0 | 21ms | 59488kb | C++17 | 1.6kb | 2023-06-12 20:48:27 | 2023-06-12 20:48:29 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int n,a[100011],tot,m,b[100011],sum[15011],buc[15011],nxt[15011];
vector<bitset<15011> > dp[15011];
bitset<15011> I;vector<int> v,tmp;
priority_queue<pii > pq;
int main()
{
scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",a+i),++buc[a[i]],tot+=a[i];
scanf("%d",&m);for(int i=1;i<=m;++i)scanf("%d",b+i);
int cnt=n;
for(int i=1;i<=15000;++i)
{
sum[i]=sum[i-1]+cnt;
cnt-=buc[i];
}
for(int i=0;i<15011;++i)I[i]=1;
dp[0].resize(m+1);dp[0][m][0]=1;
for(int i=1;i<=tot+1;++i)
{
for(int j=int(dp[i-1].size())-2;j>0;--j)
{
dp[i-1][j]=(dp[i-1][j]|dp[i-1][j+1])&(I>>15011-sum[i-1]-1);
}
if(!dp[i-1].size())break;
while(!dp[i-1].back().any())dp[i-1].pop_back();
dp[i-1].shrink_to_fit();
if(dp[i-1].size()>1&&dp[i-1][1][tot]||!dp[i-1].size())break;
if(i<=tot)
{
dp[i].resize(dp[i-1].size());
for(int j=1;j<dp[i-1].size();++j)dp[i][j]=dp[i-1][j]<<b[j];
}
}
int I=-1,J=1,K=tot;
for(int i=1;i<=tot;++i)
{
if(J<dp[i].size()&&dp[i][J][K]){I=i;break;}
}
if(!~I){printf("-1\n");return 0;}
printf("%d\n",I);
while(I!=0)
{
if(J<dp[I].size()-1&&dp[I][J+1][K])++J;
v.push_back(b[J]);--I;K-=b[J];
}
for(int i=1;i<=n;++i)pq.push(pii(a[i],i));
sort(v.begin(),v.end());
for(int i=0;i<v.size();++i)
{
printf("%d ",v[i]);
tmp.clear();
for(int _=0;_<v[i];++_)tmp.push_back(pq.top().s2),pq.pop();
for(int x:tmp)--a[x],printf("%d ",x);putchar(10);
for(int x:tmp)pq.push(pii(a[x],x));
}return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 2ms
memory: 4044kb
input:
1 1 1 1
output:
1 1 1
result:
ok good!
Test #2:
score: 0
Accepted
time: 1ms
memory: 4212kb
input:
2 1 1 1 1
output:
2 1 2 1 1
result:
ok good!
Test #3:
score: 0
Accepted
time: 2ms
memory: 4084kb
input:
2 1 1 1 2
output:
1 2 2 1
result:
ok good!
Test #4:
score: 0
Accepted
time: 2ms
memory: 4036kb
input:
2 1 1 2 1 2
output:
1 2 2 1
result:
ok good!
Test #5:
score: 0
Accepted
time: 2ms
memory: 4088kb
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: 0ms
memory: 4072kb
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: 3ms
memory: 5908kb
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: 2ms
memory: 4064kb
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: -6
Wrong Answer
time: 2ms
memory: 6588kb
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 2 500 499 3 498 497 496
result:
wrong answer there are unused item 1
Subtask #2:
score: 0
Wrong Answer
Test #28:
score: 7
Accepted
time: 2ms
memory: 4140kb
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: 2ms
memory: 5928kb
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: 3ms
memory: 15176kb
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: 21ms
memory: 59488kb
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: 1ms
memory: 4068kb
input:
2 2 1 1 1
output:
3 1 1 1 2 1 1
result:
ok good!
Test #33:
score: 0
Accepted
time: 2ms
memory: 3972kb
input:
2 1 2 1 2
output:
-1
result:
ok no solution
Test #34:
score: 0
Accepted
time: 2ms
memory: 4260kb
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
Wrong Answer
time: 2ms
memory: 4092kb
input:
3 3 2 1 1 3
output:
2 3 1 2 3 3 1 2 3
result:
wrong answer wrong plan, expected no solution
Subtask #3:
score: 0
Wrong Answer
Test #45:
score: 12
Accepted
time: 2ms
memory: 4192kb
input:
2 7 8 2 1 2
output:
8 1 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1
result:
ok good!
Test #46:
score: 0
Accepted
time: 2ms
memory: 4108kb
input:
3 5 4 6 2 2 3
output:
6 2 3 1 2 3 2 2 3 1 3 3 2 1 3 3 2 1 3 3 2 1
result:
ok good!
Test #47:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
3 4 2 9 3 1 2 3
output:
9 1 3 1 3 1 3 2 3 1 2 3 1 2 3 2 2 3 1 2 3 2 2 3 1
result:
ok good!
Test #48:
score: 0
Accepted
time: 1ms
memory: 4084kb
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: 1ms
memory: 4124kb
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: 4104kb
input:
4 3 3 6 3 3 2 3 4
output:
6 2 3 4 2 3 2 2 3 1 3 3 4 2 3 3 1 4 3 3 2 1
result:
ok good!
Test #51:
score: 0
Accepted
time: 2ms
memory: 4244kb
input:
5 4 3 3 3 1 3 2 4 5
output:
4 2 1 4 4 3 2 1 4 4 3 2 1 5 4 4 3 2 1
result:
ok good!
Test #52:
score: 0
Accepted
time: 2ms
memory: 4240kb
input:
5 4 3 3 3 2 3 3 4 5
output:
4 3 1 4 3 4 2 1 5 4 4 3 2 1 5 4 4 3 2 1
result:
ok good!
Test #53:
score: 0
Accepted
time: 2ms
memory: 4080kb
input:
5 4 4 4 2 1 3 2 4 5
output:
5 2 3 2 2 1 3 2 2 1 4 4 3 2 1 5 5 4 3 2 1
result:
ok good!
Test #54:
score: 0
Accepted
time: 1ms
memory: 4184kb
input:
5 3 3 3 3 3 3 1 2 4
output:
5 1 5 2 4 3 4 2 1 5 4 4 3 2 1 5 4 4 3 2 1
result:
ok good!
Test #55:
score: 0
Accepted
time: 1ms
memory: 4312kb
input:
6 3 3 3 2 2 2 3 2 4 6
output:
-1
result:
ok no solution
Test #56:
score: 0
Accepted
time: 2ms
memory: 4084kb
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: 2ms
memory: 4300kb
input:
6 4 4 3 2 1 1 3 1 3 5
output:
5 3 2 1 3 3 2 1 4 3 3 2 1 3 6 5 4 3 3 2 1
result:
ok good!
Test #58:
score: 0
Accepted
time: 2ms
memory: 4328kb
input:
6 7 2 2 2 1 1 5 2 3 4 5 6
output:
7 2 1 4 2 1 3 2 1 2 2 1 6 2 1 5 2 1 4 3 3 2 1
result:
ok good!
Test #59:
score: 0
Accepted
time: 0ms
memory: 4240kb
input:
7 3 3 3 2 2 1 1 3 1 4 6
output:
4 1 3 4 2 1 5 4 4 3 2 1 7 6 6 5 4 3 2 1
result:
ok good!
Test #60:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
7 4 4 3 1 1 1 1 3 1 4 6
output:
6 1 2 1 1 1 3 4 2 1 3 7 4 2 1 6 5 4 4 3 2 1
result:
ok good!
Test #61:
score: -12
Wrong Answer
time: 1ms
memory: 4284kb
input:
8 2 2 2 2 2 2 2 1 6 1 2 3 4 6 7
output:
3 2 7 6 3 5 4 3 3 2 1 8
result:
wrong answer there are unused item 1
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%