QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123290 | #5076. Prof. Pang and Ants | Crysfly | WA | 1ms | 5472kb | C++17 | 1.8kb | 2023-07-12 08:01:37 | 2023-07-12 08:01:39 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
#define i128 __int128
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 600005
#define inf 0x3f3f3f3f
int n,m,a[maxn];
struct node{
int x,y,op;
bool operator <(const node&b)const{return x<b.x;}
}b[maxn];
int cnt;
bool chk(int mid){
cnt=0;
For(i,1,n){
//(
if(mid%2==0){
b[++cnt]={a[i]+1,2,0};
b[++cnt]={mid/2+a[i]+1,-2,0};
//)
b[++cnt]={mid/2-a[i],2,1};
b[++cnt]={mid-a[i],-2,1};
}
else{
b[++cnt]={a[i]+1,2,0};
b[++cnt]={mid/2+a[i]+1,-1,0};
b[++cnt]={mid/2+a[i]+2,-1,0};
//)
b[++cnt]={mid/2-a[i],1,1};
b[++cnt]={mid/2+1-a[i],1,1};
b[++cnt]={mid-a[i],-2,1};
}
}
i128 sa=0,sb=0,res=0,now=0;
sort(b+1,b+cnt+1);
// For(i,1,cnt){
// cout<<b[i].x<<" "<<b[i].y<<" "<<b[i].op<<"\n";
// }
For(i,1,cnt-1){
if(b[i].op==0) sa+=b[i].y;
else sb+=b[i].y;
i128 t=b[i+1].x-b[i].x;
if(!t)continue;
if(sa>=sb) res+=sb*t,now+=(sa-sb)*t;
else{
now+=sa*t;
i128 tmp=min(now,sb*t);
now-=tmp;
res+=tmp;
}
}
res/=2;
// cout<<mid<<" "<<(int)res<<"\n";
return res>=m;
}
void work()
{
n=read(),m=read();
For(i,1,n)a[i]=read();
int l=0,r=114514+m+a[1]*2,res=r;
// chk(4);return;
while(l<=r){
int mid=l+r>>1;
if(chk(mid))res=mid,r=mid-1;
else l=mid+1;
}
cout<<res<<"\n";
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5432kb
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: -100
Wrong Answer
time: 1ms
memory: 5472kb
input:
1 1 100000000000000 1000000000
output:
100002000114514
result:
wrong answer 1st numbers differ - expected: '200000000000000', found: '100002000114514'