QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112668 | #6339. Cookies | Flamire | 0 | 2ms | 4148kb | C++17 | 1.6kb | 2023-06-12 20:44:10 | 2023-06-12 20:44:14 |
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],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%