QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100375 | #6339. Cookies | chenshi | 0 | 5ms | 5904kb | C++ | 1.5kb | 2023-04-25 18:57:57 | 2023-04-25 18:58:00 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int o=15010;
int n,m,a[o],a_[o],b[o],p[o],s,v[o],fa[o*2],f[o][o],cnt[o],st[o],tp,q[o];vector<int> vec[o];
inline bool cmp(int A,int B){return a[A]>a[B];}
inline bool Cmp(int A,int B){return st[A]>st[B];}
int fr(int x){return fa[x]==x?x:fa[x]=fr(fa[x]);}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),p[i]=i,s+=a[i];
sort(p+1,p+n+1,cmp);
scanf("%d",&m);
for(int i=1;i<=m;++i) scanf("%d",&b[i]);
for(int i=n;i;--i) a_[i]=a_[i+1]+a[p[i]];
for(int i=s+1;i<=s*2;++i) fa[i]=i;
f[m+1][0]=1;
for(int i=m;i;--i){
for(int j=0;j<=s;++j) fa[j]=j;
for(int j=0,k=1;j<=s;j+=b[i]-b[i-1],++k) v[j]=k;
for(int j=s,lim;j+1;--j) if(f[i+1][j]){
lim=(s-j)/b[i];
for(int k=b[i];k>b[i-1];--k) lim=min(lim,(a_[k]-j)/(b[i]-k+1));
lim=j+(b[i]-b[i-1])*lim;
for(int t=j+(b[i]-b[i-1])*(f[i+1][j]-1);t<=lim&&(t=fr(t))<=lim;t=fa[t]) f[i][t]=v[t-j],fa[t]=t+b[i]-b[i-1];
}
}
if(f[1][s]==o){printf("-1");return 0;}
printf("%d\n",f[1][s]-1);
for(int i=1,j=s;i<=m;++i) cnt[i]=--f[i][j],j-=(b[i]-b[i-1])*f[i][j];
for(int i=1;i<=m;++i) for(int j=cnt[i]-cnt[i+1];j--;) st[++tp]=b[i];
for(int i=1;i<=tp;++i) q[i]=i;
for(int i=1;i<=n;++i){
nth_element(q+1,q+a[p[i]],q+tp+1,Cmp);
for(int j=1;j<=a[p[i]];++j) vec[q[j]].push_back(p[i]),--st[q[j]];
}
for(int i=1;i<=tp;++i,putchar('\n')){
printf("%llu ",vec[i].size());
for(int j=vec[i].size();j--;) printf("%d ",vec[i][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: 2ms
memory: 3456kb
input:
1 1 1 1
output:
1 1 1
result:
ok good!
Test #2:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
2 1 1 1 1
output:
2 1 1 1 2
result:
ok good!
Test #3:
score: 0
Accepted
time: 2ms
memory: 3412kb
input:
2 1 1 1 2
output:
1 2 2 1
result:
ok good!
Test #4:
score: 0
Accepted
time: 1ms
memory: 3332kb
input:
2 1 1 2 1 2
output:
1 2 2 1
result:
ok good!
Test #5:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
4 1 1 1 1 2 2 3
output:
2 2 4 1 2 3 2
result:
ok good!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3340kb
input:
8 1 1 1 1 1 1 1 1 3 1 4 5
output:
2 4 8 5 4 1 4 7 6 3 2
result:
ok good!
Test #7:
score: 0
Accepted
time: 2ms
memory: 3448kb
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 468 1 91 1 27 1 214 1 405 1 266 1 244 1 151 1 57 1 314 1 500 1 122 1 435 1 312 1 133 1 182 1 228 1 282 1 389 1 75 1 453 1 330 1 11 1 198 1 41 1 361 1 484 1 106 1 419 1 296 1 167 1 288 1 179 1 304 1 427 1 114 1 492 1 369 1 49 1 206 1 19 1 338 1 461 1 8...
result:
ok good!
Test #8:
score: 0
Accepted
time: 2ms
memory: 3468kb
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 158 159 160 161 162 163 164 165 166 167 168 169 170 171 1 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 172 127 128 129 130 131 132 133 134 135 136 137 138 139 140 157 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 141 221 222 223 224 225 226 227 228 229 230 231 232 ...
result:
ok good!
Test #9:
score: 0
Accepted
time: 5ms
memory: 5904kb
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 1 158 499 159 160 161 162 163 164 165 166 167 168 169 170 171 1 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 172 127 128 129 130 131 132 133 134 135 136 137 138 139 140 157 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 141 221 222 223 224 225 226 227 228 229 230 231 2...
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: 2ms
memory: 3468kb
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: 3440kb
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: 2ms
memory: 3504kb
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: 5ms
memory: 4112kb
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: 2ms
memory: 3336kb
input:
2 2 1 1 1
output:
3 1 1 1 1 1 2
result:
ok good!
Test #33:
score: -7
Runtime Error
input:
2 1 2 1 2
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #45:
score: 12
Accepted
time: 2ms
memory: 3308kb
input:
2 7 8 2 1 2
output:
8 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2
result:
ok good!
Test #46:
score: 0
Accepted
time: 2ms
memory: 5456kb
input:
3 5 4 6 2 2 3
output:
6 2 2 3 2 1 3 2 1 3 3 2 1 3 3 2 1 3 3 2 1 3
result:
ok good!
Test #47:
score: 0
Accepted
time: 2ms
memory: 5232kb
input:
3 4 2 9 3 1 2 3
output:
9 1 3 1 3 1 3 1 3 1 3 2 1 3 2 1 3 3 2 1 3 3 2 1 3
result:
ok good!
Test #48:
score: 0
Accepted
time: 2ms
memory: 5344kb
input:
4 3 5 4 3 2 3 4
output:
5 3 1 3 2 3 4 3 2 3 1 3 2 3 4 3 2 3 4 1 2
result:
ok good!
Test #49:
score: 0
Accepted
time: 2ms
memory: 3416kb
input:
4 1 4 5 5 3 1 3 4
output:
5 3 2 4 3 3 1 4 3 3 2 4 3 3 2 4 3 3 2 4 3
result:
ok good!
Test #50:
score: 0
Accepted
time: 0ms
memory: 5448kb
input:
4 3 3 6 3 3 2 3 4
output:
6 2 2 3 2 1 3 2 2 3 2 4 3 3 4 1 3 4 4 2 1 3
result:
ok good!
Test #51:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
5 4 3 3 3 1 3 2 4 5
output:
4 2 4 1 4 4 3 2 1 4 5 3 2 1 4 4 3 2 1
result:
ok good!
Test #52:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
5 4 3 3 3 2 3 3 4 5
output:
4 3 4 3 1 3 4 2 1 4 5 3 2 1 5 5 4 3 2 1
result:
ok good!
Test #53:
score: 0
Accepted
time: 2ms
memory: 3316kb
input:
5 4 4 4 2 1 3 2 4 5
output:
5 2 3 1 2 3 2 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: 3316kb
input:
5 3 3 3 3 3 3 1 2 4
output:
5 1 4 2 5 3 4 4 3 2 1 4 5 3 2 1 4 5 4 2 1
result:
ok good!
Test #55:
score: -12
Runtime Error
input:
6 3 3 3 2 2 2 3 2 4 6
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%