QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104890#4790. InheritanceDeterminantWA 2ms3828kbC++141.1kb2023-05-12 11:44:132023-05-12 11:44:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 11:44:14]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3828kb
  • [2023-05-12 11:44:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;const int N=1e6+7;
int n;typedef long long ll;typedef long double ld;
ll x,minn=2e18,maxx,mn,mx,l[N],r[N],a[N],ans=2e18,a1,a2;
ll calc(ll x,ll y){return max(y-x,(x+minn-1)/minn-y/maxx);}
int main(){
	scanf("%d%lld",&n,&x);for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]),minn=min(minn,a[i]),maxx=max(maxx,a[i]);
	}
	ld t=(ld)maxx/minn*(minn+1)/(maxx+1),s=0;
	for(int i=1;i<=n;++i)s+=(a[i]==minn?1:t);
	mn=(ll)((ld)x/s);mx=(ll)((ld)x/s*t);
	for(ll i=mn-2;i<=mn+2;++i)for(ll j=mx-2;j<=mx+2;++j){
		int fl=1;ll sl=0,sr=0;for(int k=1;k<=n;++k){
			l[k]=max(j/maxx*a[k],i);r[k]=min((i+minn-1)/minn*a[k],j);
			if(l[k]>r[k]){fl=0;break;}sl+=l[k];sr+=r[k];
		}
		if(!fl||x<sl||x>sr)continue;
		if(calc(i,j)<ans)ans=calc(i,j),a1=i,a2=j;
	}
	ll sl=0,sr=0,i=a1,j=a2;for(int k=1;k<=n;++k){
		l[k]=max(j/maxx*a[k],i);r[k]=min((i+minn-1)/minn*a[k],j);
		sl+=l[k];sr+=r[k];
	}
	printf("%lld\n",ans);ll u=x-sl;
	for(int k=1;k<=n;++k){
		if(u>=r[k]-l[k])printf("%lld ",r[k]),u-=r[k]-l[k];
		else printf("%lld ",l[k]+u),u=0;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3816kb

input:

2 100
1 2


output:

15
43 57 

result:

ok DIFF = 15

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3828kb

input:

4 32
1 1 1 2

output:

4
7 7 7 11 

result:

wrong answer you claimed 4, but the expected DIFF is 3