QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326587#8225. 最小值之和linrui36 57ms4728kbC++142.9kb2024-02-13 15:00:102024-02-13 15:00:10

Judging History

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

  • [2024-02-13 15:00:10]
  • 评测
  • 测评结果:36
  • 用时:57ms
  • 内存:4728kb
  • [2024-02-13 15:00:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using u64=unsigned long long;
using LF=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define CT const&
#define IL inline
#define PB push_back
template<class T>
IL void tomn(T &x,T CT y){y<x?x=y,0:0;}
template<class T>
IL void tomx(T &x,T CT y){y>x?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
const LF EPS=1e-10L;
IL int dcmp(LF x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const LL INF=4e18L;

const int N=85;
int n,g[N];
namespace S1{
	const int N=15;
	LF a[N][N],x[N];
	bool calc(){
		int row=1;
		F(i,1,n-1){
			int p=-1;
			F(j,row,n)if(dcmp(a[j][i]))p=j;
			if(p==-1)continue;
			F(j,i,n)swap(a[row][j],a[p][j]);
			F(j,row+1,n){
				LF x=a[j][i]/a[row][i];
				F(k,i,n)a[j][k]-=x*a[row][k];
			}++row;
		}F(i,1,n-1)x[i]=0;
		F(i,row,n)if(dcmp(a[i][n]))return 0;
		G(i,row-1,1){
			int p=1;
			while(p<=n&&!dcmp(a[i][p]))++p;
			if(p>n)continue;
			x[p]=a[i][n]/a[i][p];
			F(j,1,i-1)a[j][n]-=a[j][p]*x[p],a[j][p]=0;
		}return 1;
	}
	bool main(){
		int f[N]{},p[N]{};
		F(i,1,n-1)p[i]=i;
		do{
			
			vector<int> vec{p+1,p+n};
			if(vec==vector<int>{3,1,4,2,5,6}){
				cerr<<"!!!\n";
			}
			
			F(i,0,N-1)F(j,0,N-1)a[i][j]=0;
			F(i,1,n){
				int mn;
				mn=n+1;G(j,i-1,1)tomn(mn,p[j]),a[i][mn]+=1;
				mn=n+1;F(j,i,n-1)tomn(mn,p[j]),a[i][mn]+=1;
				G(j,n-1,2)a[i][j-1]+=a[i][j];
				a[i][n]=g[i];
			}if(calc()){
				F(i,2,n-1)x[i]+=x[i-1];
				F(i,2,n-1)if(dcmp(x[i]-x[i-1])<0)goto ED;
				F(i,1,n-1)if(dcmp(x[i]-LL(x[i]+.5L)))goto ED;
				F(i,1,n-1)f[i]=x[p[i]]+.5L;
				F(i,1,n-1)if(f[i]<0)goto ED;
				goto OK;
			}ED:;
		}while(next_permutation(p+1,p+n));
		return 0;
	OK:
		puts("Yes");
		F(i,1,n-1)printf("%d ",f[i]);
		return 1;
	}
}
namespace S2{
	const int N=55,W=55;
	using D=bitset<N*W+100>;
	D f[N][N];
	int ans[N];
	void dfs(int l,int r,int i){
		if(l==r)return;
		F(m,l,r-1)F(x,0,100000){
			if(i+x*(r-l)>n*W)break;
			if(f[l][m][i+x*(r-l)]&&f[m+1][r][i+x*(r-l)]){
				F(j,l,r-1)ans[j]+=x;
				return dfs(l,m,i+x*(r-l)),dfs(m+1,r,i+x*(r-l));
			}
		}
	}
	bool main(){
		G(l,n,1)F(r,l,n){
			f[l][r]=D{};
			if(l==r){
				f[l][r][g[l]]=1;
				
//				cerr<<l<<" "<<r<<" ";
//				F(i,0,10)cerr<<f[l][r][i];
//				cerr<<endl;
				
				continue;
			}
			F(m,l,r-1){
				D d=f[l][m]&f[m+1][r];
				G(i,n*W,0){
					if(!d[i])continue;
					int j=i;
					while(j>=0&&!f[l][r][j])
						f[l][r][j]=1,j-=(r-l);
				}
			}
			
//			cerr<<l<<" "<<r<<" ";
//			F(i,0,10)cerr<<f[l][r][i];
//			cerr<<endl;
				
		}if(!f[1][n][0])return 0;
		dfs(1,n,0),puts("Yes");
		F(i,1,n-1)printf("%d ",ans[i]);
		return 1;
	}
}
int main(){
#ifdef LOCAL
	freopen("B.in","r",stdin);
//	freopen(".out","w",stdout);
#endif
	scanf("%d",&n);
	F(i,1,n)scanf("%d",g+i);
	if(!S2::main())
		puts("No");
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 1ms
memory: 3820kb

input:

5
14 14 12 13 13

output:

Yes
14 0 6 7 

result:

ok The answer is correct.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1 

result:

ok The answer is correct.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4 

result:

ok The answer is correct.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

5
11 11 10 5 5

output:

Yes
6 5 0 5 

result:

ok The answer is correct.

Test #5:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

5
10 10 10 4 4

output:

Yes
5 5 0 4 

result:

ok The answer is correct.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1 

result:

ok The answer is correct.

Test #7:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

5
2 2 6 11 11

output:

Yes
2 0 3 8 

result:

ok The answer is correct.

Test #9:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

5
10 10 8 5 5

output:

Yes
6 4 0 5 

result:

ok The answer is correct.

Test #10:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7 

result:

ok The answer is correct.

Test #11:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

5
5 5 22 31 31

output:

Yes
5 0 11 20 

result:

ok The answer is correct.

Test #12:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

5
8 33 38 38 29

output:

Yes
2 11 16 9 

result:

ok The answer is correct.

Test #13:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

5
16 16 4 12 12

output:

Yes
16 0 2 10 

result:

ok The answer is correct.

Test #14:

score: 0
Accepted
time: 0ms
memory: 4108kb

input:

5
29 29 24 26 26

output:

Yes
29 0 12 14 

result:

ok The answer is correct.

Test #15:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

5
0 33 33 32 32

output:

Yes
0 33 0 32 

result:

ok The answer is correct.

Test #16:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

5
6 7 7 6 6

output:

Yes
3 4 0 6 

result:

ok The answer is correct.

Test #23:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

5
25 25 24 20 20

output:

Yes
13 12 0 20 

result:

ok The answer is correct.

Test #24:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2
2 2

output:

Yes
2 

result:

ok The answer is correct.

Test #33:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

1
0

output:

Yes

result:

ok The answer is correct.

Test #34:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

1
233

output:

No

result:

ok The answer is correct.

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #35:

score: 15
Accepted
time: 0ms
memory: 3852kb

input:

8
16 16 8 8 9 9 6 6

output:

Yes
16 0 8 0 9 0 6 

result:

ok The answer is correct.

Test #36:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

8
16 16 9 21 21 23 23 23

output:

Yes
16 0 3 15 1 10 10 

result:

ok The answer is correct.

Test #37:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

8
10 10 15 15 15 10 10 5

output:

Yes
10 0 6 6 1 6 1 

result:

ok The answer is correct.

Test #38:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

8
13 13 15 15 24 24 24 10

output:

Yes
13 0 7 2 9 9 2 

result:

ok The answer is correct.

Test #39:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

8
5 13 16 25 25 24 4 4

output:

Yes
1 3 4 9 8 0 4 

result:

ok The answer is correct.

Test #40:

score: -15
Wrong Answer
time: 0ms
memory: 3664kb

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

No

result:

wrong answer Line 1 expected 

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 25
Accepted

Dependency #1:

100%
Accepted

Test #77:

score: 25
Accepted
time: 47ms
memory: 4412kb

input:

49
28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4

output:

Yes
14 14 0 12 25 0 15 18 1 13 27 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1 

result:

ok The answer is correct.

Test #78:

score: 0
Accepted
time: 48ms
memory: 4468kb

input:

49
3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4

output:

Yes
3 0 29 0 31 0 34 0 17 14 1 10 9 0 21 0 36 0 11 14 13 2 14 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 60 0 4 2 

result:

ok The answer is correct.

Test #79:

score: 0
Accepted
time: 48ms
memory: 4416kb

input:

49
18 18 18 16 16 59 61 64 64 57 57 78 78 78 78 81 92 92 92 92 89 81 47 64 64 63 59 65 65 63 52 52 34 34 33 8 13 13 17 17 14 16 19 19 13 13 18 18 18

output:

Yes
9 9 0 16 0 19 20 23 1 53 0 78 0 78 0 36 47 1 28 25 21 3 8 15 14 12 0 31 29 1 46 1 15 14 0 4 9 0 17 0 3 4 7 1 6 1 6 6 

result:

ok The answer is correct.

Test #80:

score: 0
Accepted
time: 52ms
memory: 4464kb

input:

50
43 47 47 42 42 41 51 51 57 62 62 61 58 58 67 67 68 68 63 68 68 67 71 71 76 76 76 76 76 76 48 48 48 48 36 36 33 33 4 8 8 6 6 11 11 3 3 10 10 10

output:

Yes
20 24 1 20 19 0 51 0 19 22 21 0 58 0 67 0 68 0 21 24 23 0 71 0 76 0 76 0 76 0 48 0 48 0 36 0 33 0 2 6 0 6 0 11 0 3 0 5 5 

result:

ok The answer is correct.

Test #81:

score: 0
Accepted
time: 48ms
memory: 4412kb

input:

49
12 14 14 16 16 10 18 32 32 30 30 0 0 5 5 4 0 9 9 18 18 18 30 41 43 43 39 39 35 24 26 27 27 6 6 13 13 19 22 22 21 21 44 44 43 43 33 33 31

output:

Yes
6 8 0 16 0 2 4 18 4 16 0 0 0 3 2 0 0 9 0 9 9 0 5 9 11 6 10 6 0 8 9 10 0 6 0 1 1 4 7 1 2 2 25 2 24 2 9 7 

result:

ok The answer is correct.

Test #82:

score: 0
Accepted
time: 39ms
memory: 4448kb

input:

48
13 13 11 3 36 40 40 40 36 35 35 30 18 18 33 33 33 23 20 20 17 19 20 20 0 10 31 31 28 30 30 5 16 16 13 12 12 36 39 39 37 37 25 25 26 26 7 7

output:

Yes
7 5 1 0 9 11 11 9 0 20 15 0 14 1 12 12 7 0 16 1 5 6 7 0 0 5 26 0 14 16 0 1 8 5 1 8 0 18 21 0 37 0 25 0 26 0 7 

result:

ok The answer is correct.

Test #83:

score: 0
Accepted
time: 47ms
memory: 4728kb

input:

49
72 72 71 33 98 98 89 89 174 174 163 163 170 170 82 98 98 202 202 179 164 282 299 299 316 316 300 262 250 250 236 154 140 148 150 150 148 148 131 95 95 106 106 108 108 81 78 78 51

output:

Yes
31 30 11 0 98 0 89 0 174 0 163 0 170 0 41 57 0 98 75 1 40 99 116 3 105 89 70 5 89 75 34 1 33 37 39 2 61 44 2 50 2 61 2 46 19 2 31 4 

result:

ok The answer is correct.

Test #84:

score: 0
Accepted
time: 51ms
memory: 4476kb

input:

50
148 360 360 392 392 399 399 384 350 350 346 346 306 306 314 314 346 346 323 321 174 293 299 304 342 342 340 328 328 227 227 192 330 339 339 318 327 327 326 266 266 182 204 204 67 67 79 79 85 85

output:

Yes
74 286 0 392 0 207 192 0 350 0 346 0 306 0 314 0 131 108 107 0 21 38 39 40 60 58 40 64 3 200 0 64 133 142 0 106 111 110 0 266 0 91 113 0 67 0 79 0 85 

result:

ok The answer is correct.

Test #85:

score: 0
Accepted
time: 40ms
memory: 4700kb

input:

48
200 224 224 200 267 267 259 231 246 246 215 215 196 184 180 180 270 270 270 234 230 233 233 186 114 165 165 160 190 212 212 243 243 239 239 143 143 162 162 262 264 264 246 234 238 238 22 22

output:

Yes
100 124 0 31 67 59 32 45 60 1 74 55 49 3 137 3 81 81 63 5 69 72 47 0 57 108 0 32 47 69 32 115 0 239 0 143 0 162 0 90 92 82 0 117 121 0 22 

result:

ok The answer is correct.

Test #86:

score: 0
Accepted
time: 43ms
memory: 4456kb

input:

49
226 226 216 196 196 158 193 253 253 257 257 257 201 300 300 320 384 392 392 385 385 263 291 291 269 287 287 277 277 487 487 497 497 496 482 507 511 511 503 331 152 173 189 214 214 232 232 221 191

output:

Yes
118 108 0 196 0 14 21 36 36 38 38 2 56 155 3 78 110 118 3 209 87 2 182 3 75 93 4 154 4 346 6 110 109 30 66 75 79 73 29 3 8 11 19 44 11 43 32 17 

result:

ok The answer is correct.

Test #87:

score: 0
Accepted
time: 47ms
memory: 4456kb

input:

49
247 247 231 383 383 381 379 398 398 397 391 195 200 227 227 197 197 339 339 337 344 344 379 388 388 379 343 405 405 412 412 402 402 412 412 398 398 415 430 430 382 382 384 384 341 198 122 124 124

output:

Yes
247 0 77 154 152 0 85 93 92 89 39 0 100 127 0 197 0 339 0 155 162 1 110 119 110 2 146 208 2 359 2 349 2 359 2 345 2 124 139 19 196 19 130 87 18 7 13 15 

result:

ok The answer is correct.

Test #88:

score: 0
Accepted
time: 43ms
memory: 4440kb

input:

48
196 196 284 284 280 280 263 303 387 387 388 388 343 321 321 328 328 283 283 151 157 157 164 164 198 203 203 172 166 178 259 280 294 294 288 243 239 239 235 226 226 330 333 333 302 287 295 295

output:

Yes
196 0 284 0 280 0 75 95 179 1 197 152 1 281 1 288 1 243 1 56 62 1 124 1 51 56 38 2 8 10 27 34 44 38 23 7 49 45 7 74 7 58 61 44 39 7 143 

result:

ok The answer is correct.

Test #89:

score: 0
Accepted
time: 44ms
memory: 4264kb

input:

48
244 256 256 248 253 253 269 269 250 229 229 67 252 322 261 116 372 271 372 322 333 333 393 429 429 428 347 319 294 387 234 352 370 370 317 37 193 398 10 76 215 222 222 208 344 145 171 87

output:

No

result:

ok The answer is correct.

Test #90:

score: 0
Accepted
time: 51ms
memory: 4400kb

input:

50
34 15 33 66 66 66 33 39 9 35 55 29 34 35 51 13 50 50 56 48 44 43 57 57 57 25 50 50 27 27 21 47 35 50 50 55 55 53 7 43 37 55 55 62 62 62 52 21 26 26

output:

No

result:

ok The answer is correct.

Test #91:

score: 0
Accepted
time: 57ms
memory: 4564kb

input:

49
47 64 64 64 59 74 74 3 72 19 67 71 25 61 61 58 50 49 49 58 62 70 70 69 51 70 62 62 62 62 62 54 8 41 41 41 19 40 40 20 8 24 24 20 16 16 16 19 19

output:

No

result:

ok The answer is correct.

Test #92:

score: 0
Accepted
time: 44ms
memory: 4660kb

input:

48
13 13 10 27 27 28 28 18 29 29 26 24 31 31 30 26 12 12 0 0 0 42 42 38 38 38 37 37 27 27 26 60 60 68 70 70 67 67 70 70 67 67 48 49 49 47 47 44

output:

Yes
13 0 5 22 0 19 9 0 12 9 8 0 11 10 8 1 8 0 0 0 0 42 0 19 19 0 37 0 27 0 13 47 0 34 36 0 67 0 70 0 67 0 24 25 0 25 22 

result:

ok The answer is correct.

Test #93:

score: 0
Accepted
time: 53ms
memory: 4308kb

input:

50
22 22 14 24 27 27 25 25 10 47 47 45 41 42 42 44 44 43 43 0 32 32 30 27 27 10 10 14 14 14 4 11 11 9 23 23 20 28 28 22 29 31 1 28 30 30 30 30 27 27

output:

No

result:

ok The answer is correct.

Test #94:

score: 0
Accepted
time: 47ms
memory: 4392kb

input:

49
45 69 69 73 73 73 69 69 34 34 31 47 51 54 54 58 58 56 56 53 42 42 10 10 4 7 7 60 61 61 63 63 64 66 66 62 34 49 49 49 46 40 38 43 43 13 13 10 10

output:

No

result:

ok The answer is correct.

Test #95:

score: 0
Accepted
time: 43ms
memory: 4316kb

input:

48
17 17 16 16 0 27 29 32 32 36 36 39 39 35 33 21 23 23 46 46 46 46 38 38 36 36 34 34 31 33 33 36 36 30 30 28 28 23 19 19 33 37 37 15 38 39 39 0

output:

No

result:

ok The answer is correct.

Test #96:

score: 0
Accepted
time: 47ms
memory: 4348kb

input:

49
18 25 25 24 30 31 31 32 32 31 27 43 43 48 48 53 53 51 39 48 48 47 47 11 11 53 28 24 24 23 21 24 24 24 24 19 38 39 39 38 38 39 42 42 41 36 39 39 37

output:

No

result:

ok The answer is correct.

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%