QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#518559 | #5076. Prof. Pang and Ants | zhouhuanyi | WA | 22ms | 5928kb | C++14 | 1.9kb | 2024-08-13 22:04:09 | 2024-08-13 22:04:09 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 300000
using namespace std;
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];
int T,n,l,r,a[N+1],length;
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);
}
}
int main()
{
long long ps,d;
int ds;
T=read();
while (T--)
{
n=read(),m=read(),length=1,ans=0;
for (int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
for (int i=1;i<=n;++i)
if (m)
{
if (i==n) d=m/i;
else d=min(m/i,(long long)(a[i+1]-a[i]));
ans=max(ans,(long long)((a[i]+d-1-a[1])<<1)),tong[++length]=(reads){a[i],a[i]+d-1,i},m-=d*i;
}
if (m) ans=max(ans,(long long)((a[n]+1-a[n-m+1])<<1)),tong[++length]=(reads){a[n],a[n],(int)(m)};
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),ans=max(ans,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};
}
}
printf("%lld\n",ans+2);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
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: 5928kb
input:
1 1 100000000000000 1000000000
output:
200000000000000
result:
ok 1 number(s): "200000000000000"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5888kb
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: 9ms
memory: 3872kb
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: 22ms
memory: 5836kb
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 134 128 122 146 114 146 113 104 186 174 164 154 168 80 169 121 129 92 186 168 169 207 114 166 165 150 98 129 183 171 225 158 117 94 128 190 142 144 187 152 187 184 138 177 166 149 90 179 176 106 64 130 188 185 126 142 110 102 104 150 130 191 102 166 214 116 166 136 187 206 170...
result:
wrong answer 7th numbers differ - expected: '114', found: '134'