QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331845#5076. Prof. Pang and AntsC1942huangjiaxuWA 0ms3792kbC++141.1kb2024-02-18 20:26:552024-02-18 20:26:55

Judging History

你现在查看的是最新测评结果

  • [2024-02-18 20:26:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-02-18 20:26:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int T,n,a[N],cp;
ll m;
struct opt{
	ll x;int t,c;
	bool operator <(const opt b)const{return x<b.x;}
}p[N*6];
bool check(ll t){
	cp=0;
	ll h=t>>1;
	for(int i=1;i<=n;++i){
		if(t&1){
			p[++cp]={a[i]+1,0,2};
			p[++cp]={a[i]+h+1,0,-1};
			p[++cp]={a[i]+h+2,0,-1};
			p[++cp]={h-a[i],1,1};
			p[++cp]={h-a[i]+1,1,1};
			p[++cp]={t-a[i],1,-2};
		}else{
			p[++cp]={a[i]+1,0,2};
			p[++cp]={a[i]+h+1,0,-2};
			p[++cp]={h-a[i],1,2};
			p[++cp]={t-a[i],1,-2};
		}
	}
	ll sf=0,st=0,res=0,rs;
	sort(p+1,p+cp+1);
	for(int i=1;i<cp;++i){
		if(!p[i].t)sf+=p[i].c;
		else st+=p[i].c;
		ll dt=p[i+1].x-p[i].x;
		if(!dt)continue;
		if(sf>=st)res+=st*dt,rs+=(sf-st)*dt;
		else{
			rs+=sf*dt;
			ll u=min(st*dt,rs);
			rs-=u,res+=u;
		}
	}
	return res>=m*2;
}
void solve(){
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	ll l=2*m/n,r=2.1e14;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3792kb

input:

3
2 4
1 2
3 10
1 2 3
5 1
1 2 3 4 5

output:

6
9
3

result:

wrong answer 3rd numbers differ - expected: '4', found: '3'