QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#519070#5076. Prof. Pang and AntszhouhuanyiTL 4ms16200kbC++143.0kb2024-08-14 15:55:222024-08-14 15:55:23

Judging History

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

  • [2024-08-14 15:55:23]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:16200kb
  • [2024-08-14 15:55:22]
  • 提交

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,pst=1,pst2=1,pst3=1;
	long long ps,dst=(x&1)?m<<1:m,res=0;
	__int128 tres=0;
	leng=0,length=1;
	if (!(x&1))
	{
		tres=(__int128)(x>>1)*n;
		while (pst<=n||pst2<=n)
		{
			if (pst<=n&&(pst2>n||a[pst]<a[pst2]+(x>>1))) st[++leng]=(rds){a[pst],1},++pst;
			else st[++leng]=(rds){a[pst2]+(x>>1),-1},++pst2;
		}
		
	}
	else
	{
		tres=x*n;
		while (pst<=n||pst2<=n||pst3<=n)
		{
			if (pst<=n&&(pst2>n||a[pst]<a[pst2]+(x>>1))&&(pst3>n||a[pst]<a[pst3]+(x>>1)+1)) st[++leng]=(rds){a[pst],2},++pst;
			else if (pst3>n||a[pst2]<a[pst3]+1) st[++leng]=(rds){a[pst2]+(x>>1),-1},++pst2;
			else st[++leng]=(rds){a[pst3]+(x>>1)+1,-1},++pst3;
		}
	}
	if (tres<dst) return 0;
	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,ps=tong[r].r+1;
			if (tong[r].l>tong[r].r) r--;
			if (ds) 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,ps=tong[l].l-1;
			if (tong[l].l>tong[l].r) l++;
			if (ds) 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: 3ms
memory: 16200kb

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: 3ms
memory: 16072kb

input:

1
1 100000000000000
1000000000

output:

200000000000000

result:

ok 1 number(s): "200000000000000"

Test #3:

score: 0
Accepted
time: 4ms
memory: 14208kb

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: -100
Time Limit Exceeded

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: