QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519070 | #5076. Prof. Pang and Ants | zhouhuanyi | TL | 4ms | 16200kb | C++14 | 3.0kb | 2024-08-14 15:55:22 | 2024-08-14 15:55:23 |
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+1)*d2)+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,pst=1,pst2=1,pst3=1;
long long ps,dst=(x&1)?m<<1:m,res=0;
__int128 tres=0;
leng=0,length=1;
if (!(x&1))
{
tres=(__int128)(x>>1)*n;
while (pst<=n||pst2<=n)
{
if (pst<=n&&(pst2>n||a[pst]<a[pst2]+(x>>1))) st[++leng]=(rds){a[pst],1},++pst;
else st[++leng]=(rds){a[pst2]+(x>>1),-1},++pst2;
}
}
else
{
tres=x*n;
while (pst<=n||pst2<=n||pst3<=n)
{
if (pst<=n&&(pst2>n||a[pst]<a[pst2]+(x>>1))&&(pst3>n||a[pst]<a[pst3]+(x>>1)+1)) st[++leng]=(rds){a[pst],2},++pst;
else if (pst3>n||a[pst2]<a[pst3]+1) st[++leng]=(rds){a[pst2]+(x>>1),-1},++pst2;
else st[++leng]=(rds){a[pst3]+(x>>1)+1,-1},++pst3;
}
}
if (tres<dst) return 0;
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;
if (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,ps=tong[r].r+1;
if (tong[r].l>tong[r].r) r--;
if (ds) 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,ps=tong[l].l-1;
if (tong[l].l>tong[l].r) l++;
if (ds) 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: 3ms
memory: 16200kb
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: 3ms
memory: 16072kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: 0
Accepted
time: 4ms
memory: 14208kb
input:
1 10 1 1 1 1 1 1 1 1 1 1 1
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: -100
Time Limit Exceeded
input:
100000 1 76 95 1 60 68 1 81 86 1 88 67 1 69 28 1 75 65 1 56 22 1 88 60 1 51 41 1 64 11 1 54 71 1 63 19 1 88 5 1 89 66 1 80 66 1 81 48 1 67 99 1 94 36 1 54 46 1 51 37 1 82 17 1 74 41 1 69 61 1 79 65 1 78 10 1 71 17 1 87 88 1 83 2 1 58 29 1 59 43 1 78 53 1 75 73 1 77 71 1 52 82 1 63 69 1 83 19 1 61 27...
output:
267 197 254 223 138 206 112 209 134 128 197 126 176 222 213 178 266 188 147 126 164 157 192 210 156 142 264 166 117 146 185 222 220 217 202 166 122 162 250 214 160 158 220 132 108 213 198 276 226 197 204 140 146 215 122 142 201 269 269 188 144 246 251 200 217 184 192 139 234 128 190 242 254 166 152 ...