QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104890 | #4790. Inheritance | Determinant | WA | 2ms | 3828kb | C++14 | 1.1kb | 2023-05-12 11:44:13 | 2023-05-12 11:44:14 |
Judging History
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;
}
}
詳細信息
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