QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#21634	#2848. 城市地铁规划	s8194272^#	WA	7ms	3888kb	C++14	2.3kb	2022-03-07 17:15:45	2022-05-08 03:45:12

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-08 03:45:12]
评测

测评结果：WA
用时：7ms
内存：3888kb

查看

[2022-03-07 17:15:45]
提交

answer

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>

#define int long long
#define fi first
#define se second
#define max Max
#define min Min
#define abs Abs
#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define fan(x) (((x-1)^1)+1)
#define mp(x,y) make_pair(x,y)
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define INF 0x3f3f3f3f

using namespace std;

inline int read()
{
	int ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=(ans<<1)+(ans<<3)+c-'0';c=getchar();}
	return ans*f;
}

inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x/10) write(x/10);
	putchar((char)(x%10)+'0');
}

template<typename T>inline T Abs(T a){return a>0?a:-a;};
template<typename T,typename TT>inline T Min(T a,TT b){return a<b?a:b;}
template<typename T,typename TT> inline T Max(T a,TT b){return a<b?b:a;}

const int N=5005;
int n,k,m,p,a[15],b[N],f[N],dp[N*2],du[N],pre[N*2];

priority_queue<int> qu;

void find(int x)
{
	if(!pre[x]) return;
	find(x-pre[x]+1);
	du[++p]=pre[x];
}

struct Edge
{
	int u,v;
}e[N];
int tot;

signed main()
{
	n=read();k=read();
	for(int i=0;i<=k;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
	{
		int res=0,mod=59393;
		for(int j=0,p=1;j<=k;++j,p=p*i%mod)
			res=(res+p*a[j]%mod)%mod;
		f[i]=res;
	}
	if(n==1)
	{
		write(0);putchar(' ');write(1);
		return 0;
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[n]=f[1]*n;
	for(int i=2;i<=n;++i)
		for(int j=n;j<=n*2-2;++j)
			if(dp[j+i-1]<dp[j]+f[i]-f[1])
			{
				dp[j+i-1]=dp[j]+f[i]-f[1];
				pre[j+i-1]=i;
			}
	write(n-1);putchar(' ');
	write(dp[2*n-2]);puts("");
	find(2*n-2);
	for(int i=p+1;i<=n;++i)
		du[++p]=1;
	p=0;
	for(int i=1;i<=n;++i)
		for(int j=2;j<=du[i];++j)
			b[++p]=i;
	for(int i=1;i<=n;++i)
		if(du[i]==1)
			qu.push(-i);
	for(int i=1;i<=n-2;++i)
	{
		int u=-qu.top();qu.pop();
		e[++tot]=(Edge){u,b[i]};
		if(--du[b[i]]==1) qu.push(-b[i]);
	}
	e[++tot]=(Edge){-qu.top(),n};
	for(int i=1;i<=n-1;++i)
		write(e[i].u),putchar(' '),write(e[i].v),puts("");
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 3668kb

input:

63 7
4 50 14 48 33 13 44 24

output:

result:

ok

Test #2:

score: 0

Accepted

time: 3ms

memory: 3756kb

input:

208 7
23 28 14 16 46 28 26 28

output:

207 3317121
104 1
105 1
1 2
106 2
2 3
107 3
3 4
108 4
4 5
109 5
5 6
110 6
6 7
111 7
7 8
112 8
8 9
113 9
9 10
114 10
10 11
115 11
11 12
116 12
12 13
117 13
13 14
118 14
14 15
119 15
15 16
120 16
16 17
121 17
17 18
122 18
18 19
123 19
19 20
124 20
20 21
125 21
21 22
126 22
22 23
127 23
23 24
128 24
24...

result:

ok

Test #3:

score: 0

Accepted

time: 7ms

memory: 3888kb

input:

2928 3
27 20 7 29

output:

2927 13889888
267 1
268 1
269 1
270 1
271 1
272 1
273 1
274 1
275 1
276 1
277 1
1 2
278 2
279 2
280 2
281 2
282 2
283 2
284 2
285 2
286 2
287 2
2 3
288 3
289 3
290 3
291 3
292 3
293 3
294 3
295 3
296 3
297 3
3 4
298 4
299 4
300 4
301 4
302 4
303 4
304 4
305 4
306 4
307 4
4 5
308 5
309 5
310 5
311 5
...

result:

ok

Test #4:

score: 0

Accepted

time: 2ms

memory: 3796kb

input:

320 3
46 42 15 15

output:

319 1260206
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
1 2
34 2
35 2
36 2
37 2
38 2
39 2
40 2
41 2
42 2
43 2
44 2
45 2
46 2
2 3
47 3
48 3
49 3
50 3
51 3
52 3
53 3
54 3
55 3
56 3
57 3
58 3
59 3
3 4
60 4
61 4
62 4
63 4
64 4
65 4
66 4
67 4
68 4
69 4
70 4
71 4
72 4
4 5
73 5
74 5
75 5
76 5
77 5
78...

result:

ok

Test #5:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

380 5
41 27 8 3 31 0

output:

379 3140470
77 1
78 1
79 1
1 2
80 2
81 2
82 2
83 2
2 3
84 3
85 3
86 3
87 3
3 4
88 4
89 4
90 4
91 4
4 5
92 5
93 5
94 5
95 5
5 6
96 6
97 6
98 6
99 6
6 7
100 7
101 7
102 7
103 7
7 8
104 8
105 8
106 8
107 8
8 9
108 9
109 9
110 9
111 9
9 10
112 10
113 10
114 10
115 10
10 11
116 11
117 11
118 11
119 11
11...

result:

ok

Test #6:

score: 0

Accepted

time: 2ms

memory: 3688kb

input:

365 5
35 20 24 29 3 25

output:

364 3508667
122 1
123 1
124 1
1 2
125 2
126 2
2 3
127 3
128 3
3 4
129 4
130 4
4 5
131 5
132 5
5 6
133 6
134 6
6 7
135 7
136 7
7 8
137 8
138 8
8 9
139 9
140 9
9 10
141 10
142 10
10 11
143 11
144 11
11 12
145 12
146 12
12 13
147 13
148 13
13 14
149 14
150 14
14 15
151 15
152 15
15 16
153 16
154 16
16 ...

result:

ok

Test #7:

score: 0

Accepted

time: 0ms

memory: 3708kb

input:

318 6
4 44 46 6 37 14 49

output:

317 6799456
159 1
160 1
1 2
161 2
2 3
162 3
3 4
163 4
4 5
164 5
5 6
165 6
6 7
166 7
7 8
167 8
8 9
168 9
9 10
169 10
10 11
170 11
11 12
171 12
12 13
172 13
13 14
173 14
14 15
174 15
15 16
175 16
16 17
176 17
17 18
177 18
18 19
178 19
19 20
179 20
20 21
180 21
21 22
181 22
22 23
182 23
23 24
183 24
24...

result:

ok

Test #8:

score: 0

Accepted

time: 3ms

memory: 3792kb

input:

416 6
30 23 4 16 45 32 19

output:

415 5383994
208 1
209 1
1 2
210 2
2 3
211 3
3 4
212 4
4 5
213 5
5 6
214 6
6 7
215 7
7 8
216 8
8 9
217 9
9 10
218 10
10 11
219 11
11 12
220 12
12 13
221 13
13 14
222 14
14 15
223 15
15 16
224 16
16 17
225 17
17 18
226 18
18 19
227 19
19 20
228 20
20 21
229 21
21 22
230 22
22 23
231 23
23 24
232 24
24...

result:

ok

Test #9:

score: 0

Accepted

time: 3ms

memory: 3804kb

input:

572 5
15 27 5 18 3 46

output:

571 9396678
191 1
192 1
193 1
1 2
194 2
195 2
2 3
196 3
197 3
3 4
198 4
199 4
4 5
200 5
201 5
5 6
202 6
203 6
6 7
204 7
205 7
7 8
206 8
207 8
8 9
208 9
209 9
9 10
210 10
211 10
10 11
212 11
213 11
11 12
214 12
215 12
12 13
216 13
217 13
13 14
218 14
219 14
14 15
220 15
221 15
15 16
222 16
223 16
16 ...

result:

ok

Test #10:

score: 0

Accepted

time: 3ms

memory: 3792kb

input:

531 8
20 13 35 27 41 43 36 25 5

output:

530 9024252
178 1
1 2
179 2
180 2
2 3
181 3
182 3
3 4
183 4
184 4
4 5
185 5
186 5
5 6
187 6
188 6
6 7
189 7
190 7
7 8
191 8
192 8
8 9
193 9
194 9
9 10
195 10
196 10
10 11
197 11
198 11
11 12
199 12
200 12
12 13
201 13
202 13
13 14
203 14
204 14
14 15
205 15
206 15
15 16
207 16
208 16
16 17
209 17
21...

result:

ok

Test #11:

score: 0

Accepted

time: 3ms

memory: 3724kb

input:

487 10
29 29 40 45 5 16 40 47 47 2 14

output:

486 18026623
486 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

result:

ok

Test #12:

score: 0

Accepted

time: 3ms

memory: 3716kb

input:

584 7
10 27 29 8 32 43 26 3

output:

583 11437238
292 1
293 1
1 2
294 2
2 3
295 3
3 4
296 4
4 5
297 5
5 6
298 6
6 7
299 7
7 8
300 8
8 9
301 9
9 10
302 10
10 11
303 11
11 12
304 12
12 13
305 13
13 14
306 14
14 15
307 15
15 16
308 16
16 17
309 17
17 18
310 18
18 19
311 19
19 20
312 20
20 21
313 21
21 22
314 22
22 23
315 23
23 24
316 24
2...

result:

ok

Test #13:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

59 4
48 16 9 42 21

output:

result:

ok

Test #14:

score: 0

Accepted

time: 3ms

memory: 3792kb

input:

561 3
22 31 17 49

output:

560 3223790
64 1
1 2
65 2
66 2
67 2
68 2
69 2
70 2
71 2
72 2
2 3
73 3
74 3
75 3
76 3
77 3
78 3
79 3
80 3
3 4
81 4
82 4
83 4
84 4
85 4
86 4
87 4
88 4
4 5
89 5
90 5
91 5
92 5
93 5
94 5
95 5
96 5
5 6
97 6
98 6
99 6
100 6
101 6
102 6
103 6
104 6
6 7
105 7
106 7
107 7
108 7
109 7
110 7
111 7
112 7
7 8
11...

result:

ok

Test #15:

score: 0

Accepted

time: 3ms

memory: 3664kb

input:

629 6
26 31 41 32 13 39 41

output:

628 13149156
315 1
1 2
316 2
2 3
317 3
3 4
318 4
4 5
319 5
5 6
320 6
6 7
321 7
7 8
322 8
8 9
323 9
9 10
324 10
10 11
325 11
11 12
326 12
12 13
327 13
13 14
328 14
14 15
329 15
15 16
330 16
16 17
331 17
17 18
332 18
18 19
333 19
19 20
334 20
20 21
335 21
21 22
336 22
22 23
337 23
23 24
338 24
24 25
3...

result:

ok

Test #16:

score: 0

Accepted

time: 3ms

memory: 3740kb

input:

616 3
38 48 27 2

output:

615 1394108
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
1 2
40 2
41 2
42 2
43 2
44 2
45 2
46 2
47 2
48 2
49 2
50 2
51 2
52 2
53 2
54 2
55 2
56 2
57 2
58 2
59 2
60 2
61 2
62 2
63 2
2 3
64 3
65 3
66 3
67 3
68 3
69 3
70 3
71 3
72 3
73 3
74 3
75 3
76 3
77 3
78 3
79 3
80 3
81 3
...

result:

ok

Test #17:

score: 0

Accepted

time: 3ms

memory: 3804kb

input:

744 2
49 45 50

output:

743 1425426
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1
37 1
38 1
39 1
1 2
40 2
41 2
42 2
43 2
44 2
45 2
46 2
47 2
48 2
49 2
50 2
51 2
52 2
53 2
54 2
55 2
56 2
57 2
58 2
59 2
60 2
61 2
62 2
63 2
64 2
65 2
66 2
67 2
68 2
69 2
70 2
71 2
2 3
72 3
73 3
74 3
75 3
76 3
77 3
78 3
79 3
...

result:

ok

Test #18:

score: 0

Accepted

time: 1ms

memory: 3872kb

input:

629 7
27 18 48 24 37 38 6 3

output:

628 9258317
159 1
1 2
160 2
2 3
161 3
162 3
163 3
3 4
164 4
165 4
166 4
4 5
167 5
168 5
169 5
5 6
170 6
171 6
172 6
6 7
173 7
174 7
175 7
7 8
176 8
177 8
178 8
8 9
179 9
180 9
181 9
9 10
182 10
183 10
184 10
10 11
185 11
186 11
187 11
11 12
188 12
189 12
190 12
12 13
191 13
192 13
193 13
13 14
194 1...

result:

ok

Test #19:

score: 0

Accepted

time: 2ms

memory: 3708kb

input:

602 8
17 25 14 13 2 16 23 24 44

output:

601 9947756
601 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

result:

ok

Test #20:

score: 0

Accepted

time: 3ms

memory: 3688kb

input:

900 2
9 13 12

output:

result:

ok

Test #21:

score: 0

Accepted

time: 3ms

memory: 3744kb

input:

839 7
12 12 28 33 35 29 14 17

output:

838 24516016
420 1
1 2
421 2
2 3
422 3
3 4
423 4
4 5
424 5
5 6
425 6
6 7
426 7
7 8
427 8
8 9
428 9
9 10
429 10
10 11
430 11
11 12
431 12
12 13
432 13
13 14
433 14
14 15
434 15
15 16
435 16
16 17
436 17
17 18
437 18
18 19
438 19
19 20
439 20
20 21
440 21
21 22
441 22
22 23
442 23
23 24
443 24
24 25
4...

result:

ok

Test #22:

score: 0

Accepted

time: 3ms

memory: 3708kb

input:

768 7
27 3 40 6 39 9 48 31

output:

767 18960055
384 1
385 1
1 2
386 2
2 3
387 3
3 4
388 4
4 5
389 5
5 6
390 6
6 7
391 7
7 8
392 8
8 9
393 9
9 10
394 10
10 11
395 11
11 12
396 12
12 13
397 13
13 14
398 14
14 15
399 15
15 16
400 16
16 17
401 17
17 18
402 18
18 19
403 19
19 20
404 20
20 21
405 21
21 22
406 22
22 23
407 23
23 24
408 24
2...

result:

ok

Test #23:

score: 0

Accepted

time: 3ms

memory: 3756kb

input:

783 3
25 19 31 45

output:

782 4263811
88 1
89 1
90 1
91 1
92 1
93 1
94 1
1 2
95 2
96 2
97 2
98 2
99 2
100 2
101 2
102 2
2 3
103 3
104 3
105 3
106 3
107 3
108 3
109 3
110 3
3 4
111 4
112 4
113 4
114 4
115 4
116 4
117 4
118 4
4 5
119 5
120 5
121 5
122 5
123 5
124 5
125 5
126 5
5 6
127 6
128 6
129 6
130 6
131 6
132 6
133 6
134 ...

result:

ok

Test #24:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

2 4
24 9 31 45 15

output:

1 248
1 2

result:

ok

Test #25:

score: 0

Accepted

time: 1ms

memory: 3728kb

input:

792 5
28 40 21 32 44 11

output:

791 6695732
265 1
1 2
266 2
267 2
2 3
268 3
269 3
3 4
270 4
271 4
4 5
272 5
273 5
5 6
274 6
275 6
6 7
276 7
277 7
7 8
278 8
279 8
8 9
280 9
281 9
9 10
282 10
283 10
10 11
284 11
285 11
11 12
286 12
287 12
12 13
288 13
289 13
13 14
290 14
291 14
14 15
292 15
293 15
15 16
294 16
295 16
16 17
296 17
29...

result:

ok

Test #26:

score: 0

Accepted

time: 3ms

memory: 3732kb

input:

939 5
35 7 31 40 25 28

output:

938 12031060
313 1
314 1
315 1
1 2
316 2
317 2
2 3
318 3
319 3
3 4
320 4
321 4
4 5
322 5
323 5
5 6
324 6
325 6
6 7
326 7
327 7
7 8
328 8
329 8
8 9
330 9
331 9
9 10
332 10
333 10
10 11
334 11
335 11
11 12
336 12
337 12
12 13
338 13
339 13
13 14
340 14
341 14
14 15
342 15
343 15
15 16
344 16
345 16
16...

result:

ok

Test #27:

score: 0

Accepted

time: 3ms

memory: 3744kb

input:

924 6
30 26 21 8 12 42 26

output:

923 14203740
462 1
463 1
1 2
464 2
2 3
465 3
3 4
466 4
4 5
467 5
5 6
468 6
6 7
469 7
7 8
470 8
8 9
471 9
9 10
472 10
10 11
473 11
11 12
474 12
12 13
475 13
13 14
476 14
14 15
477 15
15 16
478 16
16 17
479 17
17 18
480 18
18 19
481 19
19 20
482 20
20 21
483 21
21 22
484 22
22 23
485 23
23 24
486 24
2...

result:

ok

Test #28:

score: 0

Accepted

time: 3ms

memory: 3840kb

input:

902 8
8 48 35 25 32 28 21 2 44

output:

901 13244886
901 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

result:

ok

Test #29:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

1021 2
11 16 14

output:

1020 977447
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
1 2
29 2
30 2
31 2
32 2
33 2
34 2
35 2
36 2
37 2
38 2
39 2
40 2
41 2
42 2
43 2
44 2
45 2
46 2
47 2
48 2
49 2
50 2
51 2
52 2
53 2
54 2
55 2
56 2
57 2
58 2
59 2
60 2
61 2
62 2
63 2
64 2
65 2
66 2
67 2
68 2
69 2
70 2
71 2
72 2
73 2
74 2...

result:

ok

Test #30:

score: -100

Wrong Answer

time: 0ms

memory: 3584kb

input:

1 9
18 7 32 20 44 12 15 38 14 43

output:

0 1

result:

wrong answer