QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326538#8225. 最小值之和linrui#11 37ms4436kbC++142.9kb2024-02-13 13:12:182024-07-04 03:23:51

Judging History

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

  • [2024-07-04 03:23:51]
  • 评测
  • 测评结果:11
  • 用时:37ms
  • 内存:4436kb
  • [2024-02-13 13:12:18]
  • 提交

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,W){
			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: 0ms
memory: 3816kb

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: 3800kb

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: 3800kb

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: 0ms
memory: 3840kb

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: 0ms
memory: 3756kb

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: 3812kb

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: 3808kb

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: 3812kb

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: 3876kb

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: 3872kb

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: 0ms
memory: 3812kb

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: 0ms
memory: 3780kb

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: 0ms
memory: 3804kb

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: 4072kb

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: 0ms
memory: 3812kb

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: 0ms
memory: 3608kb

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

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: 3848kb

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: 3744kb

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

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

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

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

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

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: 3656kb

input:

1
0

output:

Yes

result:

ok The answer is correct.

Test #34:

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

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: 4104kb

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: 1ms
memory: 3776kb

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: 3836kb

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: 1ms
memory: 3912kb

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: 0ms
memory: 3828kb

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: 3676kb

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

No

result:

wrong answer Line 1 expected P7

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #77:

score: 25
Accepted
time: 37ms
memory: 4432kb

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: -25
Wrong Answer
time: 36ms
memory: 4436kb

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 0 0 21 25 0 20 40 0 0 0 0 0 4 2 

result:

wrong answer Your answer is wrong.

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%