QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100375#6339. Cookieschenshi0 5ms5904kbC++1.5kb2023-04-25 18:57:572023-04-25 18:58:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-25 18:58:00]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:5904kb
  • [2023-04-25 18:57:57]
  • 提交

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%