QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518962 | #5076. Prof. Pang and Ants | zhouhuanyi | WA | 516ms | 7916kb | C++14 | 2.4kb | 2024-08-14 14:47:19 | 2024-08-14 14:47:20 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 300000
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)+r2;
else return l2+get_rk(l2,r2,d2,(r1-l1+1)*d1);
}
}
bool check(long long x)
{
int rst=0,d,ds;
long long ps,dst=m,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]+(x>>1),-1},tres+=(x>>1);
if (tres<m) 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=d%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=d%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: 0ms
memory: 5924kb
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: 5836kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5876kb
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: 0
Accepted
time: 89ms
memory: 7916kb
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 ...
result:
ok 100000 numbers
Test #5:
score: -100
Wrong Answer
time: 516ms
memory: 7892kb
input:
100000 2 87 72 38 2 73 58 25 2 84 71 78 2 91 83 34 2 56 26 24 2 63 97 73 2 67 11 91 2 56 44 55 2 67 34 53 2 93 19 72 2 55 29 91 2 78 2 70 2 56 28 83 2 77 33 5 2 98 60 76 2 63 82 59 2 82 50 72 2 73 91 40 2 85 97 41 2 60 35 14 2 86 51 74 2 61 52 37 2 96 35 45 2 85 23 15 2 96 45 92 2 96 76 4 2 58 55 98...
output:
155 121 192 160 79 203 114 128 122 132 114 101 113 78 186 174 164 154 168 80 169 121 129 86 186 118 169 207 114 166 165 150 98 129 183 171 225 158 117 94 88 190 119 128 187 112 187 184 138 177 166 149 76 179 125 102 64 99 188 185 126 128 88 80 88 150 127 191 102 166 214 96 116 122 187 206 120 122 98...
result:
wrong answer 24th numbers differ - expected: '85', found: '86'