QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518993#5076. Prof. Pang and AntszhouhuanyiWA 681ms8076kbC++142.6kb2024-08-14 15:11:012024-08-14 15:11:01

Judging History

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

  • [2024-08-14 15:11:01]
  • 评测
  • 测评结果:WA
  • 用时:681ms
  • 内存:8076kb
  • [2024-08-14 15:11:01]
  • 提交

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)*d2+1)+r2;
		else return r1+get_rk(l2,r2,d2,(r2-l2+1)*d2-(r1-l1+1)*d1+1);
	}
}
bool check(long long x)
{
	int rst=0,d,ds;
	long long ps,dst=m<<1,res=0,tres=0;
	leng=0,length=1;
	for (int i=1;i<=n;++i) st[++leng]=(rds){a[i],1},st[++leng]=(rds){a[i],1},st[++leng]=(rds){a[i]+(x>>1),-1},st[++leng]=(rds){a[i]+((x+1)>>1),-1},tres+=x;
	if (tres<dst) return 0;
	sort(st+1,st+leng+1);
	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,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;
			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=(tong[l].sz-d%tong[l].sz)%tong[l].sz;
			if (tong[l].l>tong[l].r) l++;
			if (ds) ps=tong[l].l-1,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: 0ms
memory: 8076kb

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: 0ms
memory: 7940kb

input:

1
1 100000000000000
1000000000

output:

200000000000000

result:

ok 1 number(s): "200000000000000"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7936kb

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: 105ms
memory: 7892kb

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: 681ms
memory: 7900kb

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
114
128
122
132
114
101
113
78
186
174
164
154
168
80
169
121
129
85
186
118
169
207
114
166
165
150
98
129
183
171
225
158
117
94
88
190
119
128
187
112
187
184
138
177
166
149
76
179
125
102
64
99
188
185
126
128
88
80
87
150
127
191
102
166
214
96
116
122
187
206
120
122
98...

result:

wrong answer 112th numbers differ - expected: '187', found: '170'