QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100372 | #6339. Cookies | chenshi | 7 | 6ms | 4164kb | C++ | 1.6kb | 2023-04-25 18:33:46 | 2023-04-25 18:33:48 |
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=m+1;i;--i) for(int j=0;j<=s;++j) f[i][j]=o;
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]=0;
for(int i=m;i;--i){
for(int j=0;j<=s;++j) fa[j]=j;
for(int j=0,k=0;j<=s;j+=b[i]-b[i-1],++k) v[j]=k;
for(int j=s/(b[i]+1),lim;j+1;--j) if(f[i+1][j]<o){
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];(t=fr(t))<=lim;) 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]);
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
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 3332kb
input:
1 1 1 1
output:
1 1 1
result:
ok good!
Test #2:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
2 1 1 1 1
output:
2 1 1 1 2
result:
ok good!
Test #3:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
2 1 1 1 2
output:
1 2 2 1
result:
ok good!
Test #4:
score: 0
Accepted
time: 2ms
memory: 3308kb
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: -6
Wrong Answer
time: 2ms
memory: 3332kb
input:
8 1 1 1 1 1 1 1 1 3 1 4 5
output:
4 1 5 1 8 1 7 5 6 4 3 2 1
result:
wrong answer you used more buckets than jury
Subtask #2:
score: 7
Accepted
Test #28:
score: 7
Accepted
time: 2ms
memory: 3420kb
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: 1ms
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: 3ms
memory: 3484kb
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: 2ms
memory: 4164kb
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: 3404kb
input:
2 2 1 1 1
output:
3 1 1 1 1 1 2
result:
ok good!
Test #33:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
2 1 2 1 2
output:
-1
result:
ok no solution
Test #34:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
3 1 2 3 1 2
output:
3 2 2 3 2 2 3 2 1 3
result:
ok good!
Test #35:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
3 3 2 1 1 3
output:
-1
result:
ok no solution
Test #36:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
3 2 2 2 1 2
output:
3 2 2 1 2 3 1 2 3 2
result:
ok good!
Test #37:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
15 50 49 48 47 46 45 44 43 42 41 40 2 1 1 1 1 10
output:
50 10 11 10 9 7 6 5 4 3 2 1 10 11 10 8 7 6 5 4 3 2 1 10 11 10 8 7 6 5 4 3 2 1 10 10 9 8 7 6 5 4 3 2 1 10 11 9 8 7 6 5 4 3 2 1 10 10 9 8 7 6 5 4 3 2 1 10 11 10 8 7 6 5 4 3 2 1 10 11 10 9 8 7 6 5 4 2 1 10 11 10 9 8 7 6 5 4 2 1 10 12 10 9 8 6 5 4 3 2 1 10 11 10 9 8 6 5 4 3 2 1 10 11 10 9 8 6...
result:
ok good!
Test #38:
score: 0
Accepted
time: 2ms
memory: 3276kb
input:
15 51 49 48 47 46 45 44 43 42 41 40 1 1 1 1 1 10
output:
-1
result:
ok no solution
Test #39:
score: 0
Accepted
time: 4ms
memory: 3756kb
input:
10 430 3078 390 349 3750 906 377 3374 1795 551 1 4
output:
3750 4 6 2 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5 4 1 9 8 5...
result:
ok good!
Test #40:
score: 0
Accepted
time: 6ms
memory: 3892kb
input:
500 4 99 56 16 7 39 5 8 3 18 15 30 19 27 46 47 24 55 1 7 21 1 13 5 53 32 12 98 12 121 3 118 25 15 8 32 29 7 13 3 29 94 22 4 12 37 15 52 14 9 59 22 3 16 9 77 5 17 41 22 16 6 3 32 33 34 18 1 28 4 72 4 3 40 21 13 22 16 42 77 2 16 1 1 10 11 3 34 21 28 4 173 24 57 17 9 20 116 21 72 17 165 28 30 6 13 86 1...
output:
5000 3 377 316 249 3 284 395 282 3 483 395 282 3 483 395 282 3 483 395 282 3 483 395 282 3 47 395 282 3 200 395 282 3 200 395 282 3 105 395 282 3 441 395 282 3 200 395 282 3 70 395 282 3 1 395 282 3 53 395 282 3 462 395 282 3 333 46 282 3 72 395 282 3 462 395 282 3 462 395 282 3 ...
result:
ok good!
Test #41:
score: 0
Accepted
time: 4ms
memory: 3884kb
input:
500 30 23 12 48 4 11 119 12 15 24 33 9 22 46 42 7 18 49 9 1 43 3 4 43 31 11 4 7 33 30 13 5 36 3 20 2 40 37 7 1 8 43 34 12 2 37 99 38 59 36 24 18 68 23 9 24 33 1 13 10 12 2 7 7 1 5 73 7 7 32 2 13 7 49 41 20 160 69 11 61 25 35 15 22 32 66 47 45 34 14 12 7 9 43 4 42 2 24 29 16 11 6 5 5 8 11 42 3 48 20 ...
output:
200 75 189 92 41 204 332 91 168 323 334 495 237 314 180 182 299 277 221 179 403 445 198 266 11 312 358 33 253 379 478 37 254 96 21 212 246 14 421 109 18 124 424 485 302 361 407 274 465 467 327 458 86 53 368 442 398 391 303 397 484 401 131 366 200 389 47 265 196 447 489 470 316 336 297 77 284 75 468...
result:
ok good!
Test #42:
score: 0
Accepted
time: 4ms
memory: 3808kb
input:
500 6 60 24 11 17 58 8 42 30 60 38 34 54 23 5 12 32 6 35 11 60 42 35 60 25 60 37 40 5 22 24 26 17 17 60 21 7 29 13 7 56 12 8 16 8 20 11 60 12 60 32 56 30 55 12 23 26 60 60 6 18 60 60 21 21 16 28 23 60 9 16 4 8 5 20 4 60 59 39 20 8 27 8 7 6 8 10 30 18 15 60 60 41 48 17 24 17 60 10 42 6 13 22 21 14 18...
output:
60 250 72 380 101 379 219 263 369 7 121 395 99 467 411 376 488 499 225 111 497 105 185 224 203 264 443 118 34 295 110 5 362 89 298 374 328 367 249 80 496 64 409 417 438 194 103 254 431 152 317 351 31 167 158 165 424 299 240 57 490 198 475 157 255 275 67 434 156 440 233 277 38 402 53 176 125 464 244 ...
result:
ok good!
Test #43:
score: 0
Accepted
time: 4ms
memory: 3824kb
input:
122 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 ...
output:
122 121 33 34 35 36 37 38 39 40 41 42 43 44 45 46 1 48 49 50 51 52 53 54 55 56 57 58 59 60 61 47 2 3 4 5 6 7 8 9 10 11 12 13 14 15 32 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 16 94 95 96 97 98 99 100 101 102 103 104 105 106 107 62 109 110 111 112 113 114 115 116 117 118 119 120 121 122 108 63 65...
result:
ok good!
Test #44:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
498 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
3 332 158 159 162 163 164 165 168 169 170 171 174 175 176 177 180 181 182 183 186 187 172 127 130 131 132 133 136 137 138 139 142 143 144 145 148 149 150 151 154 155 156 141 222 223 224 225 228 229 230 231 188 235 236 237 240 241 242 243 246 247 248 249 190 191 192 193 196 197 198 199 202 219 204 20...
result:
ok good!
Subtask #3:
score: 0
Wrong Answer
Test #45:
score: 12
Accepted
time: 2ms
memory: 3316kb
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: 0ms
memory: 3412kb
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: 1ms
memory: 3432kb
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: 1ms
memory: 3340kb
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: -12
Wrong Answer
time: 1ms
memory: 3320kb
input:
4 1 4 5 5 3 1 3 4
output:
8 1 4 1 2 1 3 1 4 1 3 3 2 4 3 3 2 4 3 4 1 2 4 3
result:
wrong answer you used more buckets than jury
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%