QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112668#6339. CookiesFlamire0 2ms4148kbC++171.6kb2023-06-12 20:44:102023-06-12 20:44:14

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:44:14]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:4148kb
  • [2023-06-12 20:44:10]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int n,a[100011],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]];
	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<=sum[n]+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][sum[n]]||!dp[i-1].size())break;
		if(i<=sum[n])
		{
			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=sum[n];
	for(int i=1;i<=sum[n];++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||J!=m||K!=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
Runtime Error

Test #1:

score: 6
Accepted
time: 2ms
memory: 4080kb

input:

1
1
1
1

output:

1
1 1 

result:

ok good!

Test #2:

score: 0
Accepted
time: 2ms
memory: 4148kb

input:

2
1 1
1
1

output:

2
1 2 
1 1 

result:

ok good!

Test #3:

score: 0
Accepted
time: 2ms
memory: 4076kb

input:

2
1 1
1
2

output:

1
2 2 1 

result:

ok good!

Test #4:

score: 0
Accepted
time: 2ms
memory: 4092kb

input:

2
1 1
2
1 2

output:

1
2 2 1 

result:

ok good!

Test #5:

score: -6
Runtime Error

input:

4
1 1 1 1
2
2 3

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 0ms
memory: 4076kb

input:

1
15
1
1

output:

1
1 1 

result:

wrong answer there are unused item 1

Subtask #3:

score: 0
Wrong Answer

Test #45:

score: 0
Wrong Answer
time: 0ms
memory: 4096kb

input:

2
7 8
2
1 2

output:

2
2 2 1 
2 2 1 

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%