QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518997 | #5076. Prof. Pang and Ants | zhouhuanyi | WA | 1ms | 8068kb | C++14 | 2.5kb | 2024-08-14 15:12:50 | 2024-08-14 15:12:52 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define N 600000
using namespace std;
const long long inf=(long long)(3e14);
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
long long l,r;
int sz;
};
reads tong[N+1];
struct rds
{
long long num;
int data;
bool operator < (const rds &t)const
{
return num<t.num;
}
};
rds st[N+1];
int T,n,l,r,length,leng,a[N+1];
long long m,ans;
long long get_rk(long long l,long long r,long long d,long long k)
{
return l+(k+d-1)/d-1;
}
long long calc(long long l1,long long r1,int d1,long long l2,long long r2,int d2)
{
if (d1<=d2) return l1+r2;
else
{
if ((r1-l1+1)*d1>=(r2-l2+1)*d2) return get_rk(l1,r1,d1,(r2-l2)*d2+1)+l2;
else return r1+get_rk(l2,r2,d2,(r2-l2+1)*d2-(r1-l1)*d1);
}
}
bool check(long long x)
{
int rst=0,d,ds;
long long ps,dst=m<<1,res=0,tres=0;
leng=0,length=1;
for (int i=1;i<=n;++i) st[++leng]=(rds){a[i],1},st[++leng]=(rds){a[i],1},st[++leng]=(rds){a[i]+(x>>1),-1},st[++leng]=(rds){a[i]+((x+1)>>1),-1},tres+=x;
if (tres<dst) return 0;
sort(st+1,st+leng+1);
for (int i=1;i<=leng;++i)
{
rst+=st[i].data;
if (rst&&dst&&st[i].num!=st[i+1].num)
{
d=min(dst/rst,st[i+1].num-st[i].num),dst-=rst*d,tong[++length]=(reads){st[i].num,st[i].num+d-1,rst};
if (dst&&d!=st[i+1].num-st[i].num) tong[++length]=(reads){st[i].num+d,st[i].num+d,(int)(dst)},dst=0;
}
}
l=2,r=length;
while (l<=r)
{
d=min((tong[l].r-tong[l].l+1)*tong[l].sz,(tong[r].r-tong[r].l+1)*tong[r].sz),res=max(res,calc(tong[l].l,tong[l].r,tong[l].sz,tong[r].l,tong[r].r,tong[r].sz));
if (d==(tong[l].r-tong[l].l+1)*tong[l].sz&&d==(tong[r].r-tong[r].l+1)*tong[r].sz) l++,r--;
else if (d==(tong[l].r-tong[l].l+1)*tong[l].sz)
{
l++,tong[r].r-=(d+tong[r].sz-1)/tong[r].sz,ds=(tong[r].sz-d%tong[r].sz)%tong[r].sz;
if (tong[r].l>tong[r].r) r--;
if (ds) ps=tong[r].r+1,tong[++r]=(reads){ps,ps,ds};
}
else
{
r--,tong[l].l+=(d+tong[l].sz-1)/tong[l].sz,ds=(tong[l].sz-d%tong[l].sz)%tong[l].sz;
if (tong[l].l>tong[l].r) l++;
if (ds) ps=tong[l].l-1,tong[--l]=(reads){ps,ps,ds};
}
}
return res+2<=x;
}
int main()
{
T=read();
while (T--)
{
n=read(),m=read(),ans=0;
for (int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
for (int i=log(inf)/log(2);i>=0;--i)
if (ans+(1ll<<i)<=inf&&!check(ans+(1ll<<i)))
ans+=(1ll<<i);
printf("%lld\n",ans+1);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7880kb
input:
3 2 4 1 2 3 10 1 2 3 5 1 1 2 3 4 5
output:
6 9 4
result:
ok 3 number(s): "6 9 4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 8068kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7876kb
input:
1 10 1 1 1 1 1 1 1 1 1 1 1
output:
13
result:
wrong answer 1st numbers differ - expected: '4', found: '13'