QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112669#6339. CookiesFlamire0 21ms59488kbC++171.6kb2023-06-12 20:48:272023-06-12 20:48:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-12 20:48:29]
  • 评测
  • 测评结果:0
  • 用时:21ms
  • 内存:59488kb
  • [2023-06-12 20:48:27]
  • 提交

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%