QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#519012 | #5076. Prof. Pang and Ants | zhouhuanyi | WA | 739ms | 8012kb | C++14 | 2.6kb | 2024-08-14 15:25:55 | 2024-08-14 15:25:55 |
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;
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;
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;
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: 0ms
memory: 7944kb
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: 0ms
memory: 7864kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: 0
Accepted
time: 1ms
memory: 8012kb
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: 105ms
memory: 8004kb
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: 0
Accepted
time: 679ms
memory: 7960kb
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 85 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 87 150 127 191 102 166 214 96 116 122 187 206 120 122 98...
result:
ok 100000 numbers
Test #6:
score: -100
Wrong Answer
time: 739ms
memory: 8004kb
input:
100000 3 87 37 25 86 3 94 64 78 24 3 55 89 60 41 3 64 54 100 33 2 74 13 95 2 83 89 17 2 51 81 64 2 97 1 91 3 82 41 61 94 3 66 3 50 46 3 84 49 45 48 2 62 6 54 3 67 6 73 7 2 95 44 48 3 80 84 21 42 2 94 11 97 2 79 98 87 3 91 44 31 21 2 84 63 15 3 75 80 57 96 2 87 93 74 2 74 69 19 2 80 18 38 2 96 87 30 ...
output:
107 136 130 120 122 127 172 127 144 78 124 82 67 141 104 136 226 96 115 176 212 113 97 157 132 140 104 105 116 174 116 114 91 85 166 133 94 70 185 104 140 117 90 168 116 108 152 127 130 167 97 155 87 76 225 136 149 103 75 187 161 104 98 113 81 120 112 94 97 130 156 60 97 95 200 100 132 89 147 126 21...
result:
wrong answer 1204th numbers differ - expected: '140', found: '139'