QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123290#5076. Prof. Pang and AntsCrysflyWA 1ms5472kbC++171.8kb2023-07-12 08:01:372023-07-12 08:01:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 08:01:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5472kb
  • [2023-07-12 08:01:37]
  • 提交

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'