QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518559#5076. Prof. Pang and AntszhouhuanyiWA 22ms5928kbC++141.9kb2024-08-13 22:04:092024-08-13 22:04:09

Judging History

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

  • [2024-08-13 22:04:09]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:5928kb
  • [2024-08-13 22:04:09]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 300000
using namespace std;
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];
int T,n,l,r,a[N+1],length;
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 l2+get_rk(l2,r2,d2,(r1-l1+1)*d1);
	}
}
int main()
{
	long long ps,d;
	int ds;
	T=read();
	while (T--)
	{
		n=read(),m=read(),length=1,ans=0;
		for (int i=1;i<=n;++i) a[i]=read();
		sort(a+1,a+n+1);
		for (int i=1;i<=n;++i)
			if (m)
			{
				if (i==n) d=m/i;
				else d=min(m/i,(long long)(a[i+1]-a[i]));
				ans=max(ans,(long long)((a[i]+d-1-a[1])<<1)),tong[++length]=(reads){a[i],a[i]+d-1,i},m-=d*i;
			}
		if (m) ans=max(ans,(long long)((a[n]+1-a[n-m+1])<<1)),tong[++length]=(reads){a[n],a[n],(int)(m)};
		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),ans=max(ans,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=d%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=d%tong[l].sz;
				if (tong[l].l>tong[l].r) l++;
				if (ds) ps=tong[l].l-1,tong[--l]=(reads){ps,ps,ds};
			}
		}
		printf("%lld\n",ans+2);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

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: 1ms
memory: 5928kb

input:

1
1 100000000000000
1000000000

output:

200000000000000

result:

ok 1 number(s): "200000000000000"

Test #3:

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

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: 9ms
memory: 3872kb

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: 22ms
memory: 5836kb

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
134
128
122
146
114
146
113
104
186
174
164
154
168
80
169
121
129
92
186
168
169
207
114
166
165
150
98
129
183
171
225
158
117
94
128
190
142
144
187
152
187
184
138
177
166
149
90
179
176
106
64
130
188
185
126
142
110
102
104
150
130
191
102
166
214
116
166
136
187
206
170...

result:

wrong answer 7th numbers differ - expected: '114', found: '134'