QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331845 | #5076. Prof. Pang and Ants | C1942huangjiaxu | WA | 0ms | 3792kb | C++14 | 1.1kb | 2024-02-18 20:26:55 | 2024-02-18 20:26:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int T,n,a[N],cp;
ll m;
struct opt{
ll x;int t,c;
bool operator <(const opt b)const{return x<b.x;}
}p[N*6];
bool check(ll t){
cp=0;
ll h=t>>1;
for(int i=1;i<=n;++i){
if(t&1){
p[++cp]={a[i]+1,0,2};
p[++cp]={a[i]+h+1,0,-1};
p[++cp]={a[i]+h+2,0,-1};
p[++cp]={h-a[i],1,1};
p[++cp]={h-a[i]+1,1,1};
p[++cp]={t-a[i],1,-2};
}else{
p[++cp]={a[i]+1,0,2};
p[++cp]={a[i]+h+1,0,-2};
p[++cp]={h-a[i],1,2};
p[++cp]={t-a[i],1,-2};
}
}
ll sf=0,st=0,res=0,rs;
sort(p+1,p+cp+1);
for(int i=1;i<cp;++i){
if(!p[i].t)sf+=p[i].c;
else st+=p[i].c;
ll dt=p[i+1].x-p[i].x;
if(!dt)continue;
if(sf>=st)res+=st*dt,rs+=(sf-st)*dt;
else{
rs+=sf*dt;
ll u=min(st*dt,rs);
rs-=u,res+=u;
}
}
return res>=m*2;
}
void solve(){
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll l=2*m/n,r=2.1e14;
while(l<r){
ll mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%lld\n",l);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3792kb
input:
3 2 4 1 2 3 10 1 2 3 5 1 1 2 3 4 5
output:
6 9 3
result:
wrong answer 3rd numbers differ - expected: '4', found: '3'