QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116111#5280. Depot Rearrangementyoungsystem#40 86ms18432kbC++202.9kb2023-06-28 09:50:352024-05-31 14:20:43

Judging History

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

  • [2024-05-31 14:20:43]
  • 评测
  • 测评结果：40
  • 用时：86ms
  • 内存：18432kb
查看
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 09:50:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int p[200005];
int sl[200005];
bool cz[200005],vis[200005];
vector<int>v[200005];
vector<int>yy[200005],qs[200005];
int fa[200005];
int findf(int n)
{
	if(fa[n]==n)return n;
	return fa[n]=findf(fa[n]);
}
int xl1[200005],cnt1;
int xl2[200005],cnt2;
bool visd[200005];
int n,m;
void dfs(int x)
{
	if(visd[x])return;
	visd[x]=true;
	vector<int>v1;
	for(int i=1;i<=n;i++)
	{
		v1.clear();
		for(int j=0;j<yy[i].size();j++)
		{
			if(yy[i][j]==x)v1.push_back(j);
		}
		for(int j=0;j<qs[i].size();j++)
		{
			if(qs[i][j]==0)continue;
			if(!visd[qs[i][j]]&&!v1.empty())
			{
				//printf("%d %d\n",x,qs[i][j]);
				v[x].push_back(qs[i][j]);
				int sth=qs[i][j];
				yy[i][v1[v1.size()-1]]=0;
				qs[i][j]=0;
				v1.pop_back();
				dfs(sth);
			}
		}
	}
}
vector<int>wz[200005];
int now[1000005];
int sta[1000005],ttop;
void dfs1(int x)
{
	for(int i=now[x];i<v[x].size();i=now[x])
	{
		now[x]=i+1;
		dfs1(v[x][i]);
	}
	sta[++ttop]=x;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n*m;i++)
	{
		p[i]=read();
	}
	for(int i=1;i<=m;i++)fa[i]=i;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)sl[j]=0;
		for(int j=1;j<=m;j++)
		{
			sl[p[(i-1)*m+j]]++;
			if(sl[p[(i-1)*m+j]]>=2)
			{
				cz[p[(i-1)*m+j]]=true;
				qs[i].push_back(p[(i-1)*m+j]);
				wz[p[(i-1)*m+j]].push_back((i-1)*m+j);
			}
		}
		for(int j=1;j<=m;j++)if(sl[j]==0)yy[i].push_back(j);
		if(!yy[i].empty())
		{
			for(int j=1;j<yy[i].size();j++)fa[findf(yy[i][0])]=findf(yy[i][j]);
			for(int j=0;j<qs[i].size();j++)fa[findf(yy[i][0])]=findf(qs[i][j]);
		}
	} 
	for(int j=1;j<=m;j++)
	{
		if(cz[j]==false)continue;
		if(findf(j)==j)
		{
			v[m+1].push_back(j);
			v[j].push_back(m+1);
			dfs(j);
		}
	}
	for(int i=1;i<=m;i++)assert((!cz[i])||visd[i]);
	for(int i=1;i<=n;i++)
	{
		cnt1=cnt2=0;
		for(int j=0;j<yy[i].size();j++)
		{
			if(yy[i][j]!=0)xl1[++cnt1]=yy[i][j];
		}
		for(int j=0;j<qs[i].size();j++)
		{
			if(qs[i][j]!=0)xl2[++cnt2]=qs[i][j];
		}
		for(int j=1;j<=cnt1;j++)
		{
			v[xl1[j]].push_back(xl2[j]);
		}
	}
	dfs1(m+1);
	reverse(sta+1,sta+ttop+1);
	//for(int i=1;i<=ttop;i++)printf("%d ",sta[i]);
	//printf("\n");
	for(int i=1;i<=ttop;i++)
	{
		if(sta[i]==m+1)sta[i]=n*m+1;
		else
		{
			if(wz[sta[i]].empty())
			{
				sta[i]=0;
				continue;
			}
			int sth=sta[i];
			sta[i]=wz[sth][wz[sth].size()-1];
			wz[sth].pop_back();
		}
	}
	//for(int i=1;i<=ttop;i++)printf("%d ",sta[i]);
	//printf("\n");
	cnt1=0;
	for(int i=1;i<=ttop;i++)if(sta[i]!=0)sta[++cnt1]=sta[i];
	printf("%d\n",cnt1-1);
	for(int i=cnt1;i>=2;i--)printf("%d %d\n",sta[i-1],sta[i]);
	return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 5
Accepted
time: 3ms
memory: 9972kb

input:

10 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

output:

0

result:

ok both subtasks are correct!

Test #2:

score: 5
Accepted
time: 0ms
memory: 7840kb

input:

5 4
1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4

output:

13
7 21
12 7
18 12
8 18
19 8
2 19
14 2
3 14
20 3
15 20
10 15
4 10
21 4

result:

ok both subtasks are correct!

Test #3:

score: 2
Acceptable Answer
time: 2ms
memory: 7844kb

input:

10 10
8 10 10 3 7 3 5 6 1 4 3 8 2 9 1 8 4 2 7 3 10 7 9 2 1 10 10 9 1 2 9 7 4 5 2 9 10 5 7 6 6 8 6 8 4 2 9 1 2 8 6 1 4 2 2 1 5 6 3 10 10 7 9 4 8 9 8 2 5 6 4 3 1 6 3 3 10 7 7 5 3 6 8 5 9 4 6 7 9 4 10 5 3 4 5 1 1 7 8 5

output:

32
28 101
29 28
38 29
18 38
95 18
36 95
3 36
90 3
56 90
43 56
30 43
58 30
16 58
6 16
44 6
20 44
49 20
39 49
50 39
26 50
66 26
75 66
100 75
97 100
89 97
76 89
55 76
27 55
67 27
87 67
79 87
101 79

result:

points 0.40 first subtask is correct but plan is wrong.

Test #4:

score: 2
Acceptable Answer
time: 2ms
memory: 7848kb

input:

100 10
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 9 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10...

output:

19
210 1001
830 210
175 830
850 175
734 850
184 734
453 184
775 453
670 775
949 670
109 949
819 109
713 819
814 713
359 814
1001 359
747 1001
707 747
1001 707

result:

points 0.40 first subtask is correct but plan is wrong.

Test #5:

score: 0
Runtime Error

input:

200 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

result:

Test #6:

score: 2
Acceptable Answer
time: 3ms
memory: 10092kb

input:

201 20
20 18 5 5 1 7 8 17 12 10 20 12 13 19 16 2 9 8 20 20 19 10 17 20 9 11 15 17 9 2 3 4 17 10 7 20 7 19 17 11 20 2 1 13 11 9 11 6 10 8 11 3 2 16 9 15 16 12 13 6 5 13 4 13 3 8 20 18 10 3 14 1 11 20 17 17 2 11 20 1 4 10 3 3 9 13 7 10 19 16 14 16 9 19 14 15 12 9 20 12 2 19 18 2 7 7 2 12 10 8 20 18 16...

output:

1401
112 4021
29 112
11 29
28 11
59 28
140 59
120 140
239 120
80 239
33 80
95 33
280 95
34 280
40 34
313 40
132 313
64 132
429 64
144 429
4 144
57 4
149 57
18 149
92 18
12 92
340 12
176 340
47 176
273 47
53 273
39 53
37 39
164 37
531 164
38 531
55 38
60 55
271 60
70 271
150 70
76 150
153 76
155 153
...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #7:

score: 0
Runtime Error

input:

300 300
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

result:

Test #8:

score: 2
Acceptable Answer
time: 0ms
memory: 8864kb

input:

301 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

11624
6022 12041
11741 6022
11440 11741
11742 11440
11442 11742
11743 11442
11443 11743
11744 11443
11444 11744
11745 11444
11445 11745
11746 11445
11446 11746
11747 11446
11139 11747
11447 11139
11748 11447
11140 11748
11448 11140
11749 11448
11141 11749
11750 11141
11142 11750
11751 11142
11143 11...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #9:

score: 2
Acceptable Answer
time: 4ms
memory: 11184kb

input:

400 100
11 65 1 79 15 18 79 46 9 30 71 53 58 55 94 73 39 16 6 91 49 30 23 30 28 81 90 48 97 54 79 30 94 18 42 77 44 36 5 48 55 97 79 36 41 59 79 71 32 59 3 10 63 52 44 41 9 46 31 31 56 87 60 80 12 51 15 78 41 65 95 34 29 83 46 64 37 53 98 17 41 45 36 73 20 53 48 80 57 54 57 72 39 56 98 6 10 78 11 72...

output:

14592
938 40001
197 938
57 197
481 57
210 481
90 210
219 90
44 219
60 44
494 60
632 494
631 632
1866 631
277 1866
378 277
139 378
395 139
270 395
336 270
151 336
333 151
895 333
206 895
356 206
191 356
2335 191
282 2335
55 282
50 55
98 50
513 98
2336 513
41 2336
100 41
252 100
113 252
136 113
163 13...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #10:

score: 2
Acceptable Answer
time: 3ms
memory: 10032kb

input:

40 160
17 2 3 4 5 6 7 91 9 10 154 12 103 14 15 16 17 25 19 58 21 8 23 24 52 26 27 58 120 105 50 55 104 32 35 36 37 38 45 10 41 42 43 44 45 71 47 48 49 34 140 52 53 54 115 44 28 58 59 60 61 62 63 64 132 66 67 68 69 70 71 69 24 74 75 76 77 133 79 80 81 82 100 84 31 86 87 88 100 90 91 92 93 94 95 96 97...

output:

1316
1226 6401
3109 1226
1034 3109
573 1034
17 573
857 17
1504 857
305 1504
757 305
545 757
338 545
750 338
1428 750
510 1428
2991 510
1631 2991
353 1631
1803 353
1066 1803
615 1066
1876 615
705 1876
446 705
559 446
1695 559
571 1695
245 571
115 245
3072 115
938 3072
1403 938
314 1403
291 314
1178 2...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #11:

score: 2
Acceptable Answer
time: 8ms
memory: 9256kb

input:

400 100
88 82 9 2 90 1 83 32 32 79 8 79 63 67 85 82 50 63 69 2 7 91 21 90 69 3 39 78 66 83 96 53 24 65 56 63 90 54 35 55 94 22 76 12 54 55 5 49 91 73 8 19 64 54 39 23 13 27 34 4 81 52 13 11 36 45 3 50 82 81 42 50 75 15 99 70 29 26 70 66 34 15 42 83 16 19 19 12 76 1 68 49 7 17 64 37 98 34 99 37 34 64...

output:

14611
99 40001
149 99
748 149
483 748
93 483
538 93
976 538
311 976
263 311
119 263
495 119
80 495
81 80
92 81
100 92
546 100
594 546
763 594
251 763
16 251
88 16
165 88
288 165
159 288
700 159
1689 700
507 1689
63 507
24 63
134 24
378 134
37 378
186 37
1438 186
872 1438
678 872
69 678
543 69
1949 5...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #12:

score: 2
Acceptable Answer
time: 0ms
memory: 10332kb

input:

301 20
8 1 1 1 1 1 1 17 1 9 1 5 1 1 1 1 13 1 9 1 18 1 1 16 1 15 5 19 1 8 11 10 1 1 1 1 18 4 1 1 1 1 16 1 1 1 12 10 1 1 1 14 11 13 1 1 1 1 1 1 10 1 1 1 1 1 1 19 14 1 1 1 5 1 1 1 1 13 1 18 1 1 4 1 1 1 1 1 1 1 1 1 1 16 16 10 1 14 18 1 1 1 7 1 1 1 1 6 9 1 13 1 1 1 2 1 1 1 1 1 1 10 1 1 1 17 1 10 10 1 12 ...

output:

4260
186 6021
843 186
197 843
1319 197
1153 1319
2251 1153
2765 2251
19 2765
2798 19
2767 2798
2975 2767
2780 2975
3350 2780
2989 3350
4074 2989
4404 4074
4409 4404
5098 4409
5420 5098
5722 5420
5422 5722
5723 5422
37 5723
5423 37
5724 5423
830 5724
5424 830
5725 5424
1535 5725
5727 1535
1689 5727
5...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #13:

score: 2
Acceptable Answer
time: 23ms
memory: 12324kb

input:

300 300
215 159 263 206 201 183 286 56 142 10 231 214 34 54 263 250 169 208 239 148 104 22 244 17 74 68 184 52 2 30 42 83 222 106 25 152 37 225 213 213 69 273 91 221 207 48 166 28 221 50 46 64 10 254 207 109 206 144 270 291 195 197 253 235 141 186 102 68 52 24 38 6 181 44 256 200 77 233 285 163 223 ...

output:

32648
2299 90001
1195 2299
562 1195
582 562
1749 582
792 1749
572 792
2308 572
1388 2308
1025 1388
766 1025
88 766
1011 88
2697 1011
476 2697
40 476
2354 40
735 2354
752 735
1114 752
1479 1114
1941 1479
1324 1941
502 1324
2323 502
778 2323
449 778
560 449
492 560
1105 492
332 1105
119 332
826 119
29...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #14:

score: 2
Acceptable Answer
time: 56ms
memory: 13416kb

input:

201 400
1 1 1 1 1 152 1 1 1 1 1 1 1 33 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 300 154 1 1 147 1 1 1 383 186 1 1 90 256 1 1 1 1 1 1 1 63 1 1 1 1 208 1 1 1 1 31 1 1 1 1 1 1 1 127 1 1 29 216 397 393 1 1 1 1 1 1 279 1 1 1 1 55 1 1 215 249 1 1 1 1 1 1 172 1 1 1 1 1 1 1 1 1 1 1 1 349 1 331 1 1 1 1 1 1 1 34...

output:

63990
36680 80401
2704 36680
66267 2704
29714 66267
73517 29714
39804 73517
5744 39804
42749 5744
7550 42749
18389 7550
68635 18389
21900 68635
16764 21900
79195 16764
80202 79195
30686 80202
79597 30686
78794 79597
80203 78794
626 80203
35507 626
80204 35507
2610 80204
53584 2610
80205 53584
4062 8...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #15:

score: 0
Runtime Error

input:

400 400
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

result:

Test #16:

score: 2
Acceptable Answer
time: 17ms
memory: 12016kb

input:

301 200
50 129 146 60 183 51 47 77 26 73 1 45 1 44 149 1 81 196 17 16 163 35 159 71 1 94 161 138 138 27 76 1 102 42 5 186 176 1 111 198 37 63 81 155 95 164 132 135 155 194 126 98 31 34 121 19 175 148 33 105 25 122 91 165 1 69 1 197 12 98 1 155 5 53 42 1 60 98 78 61 155 13 1 171 102 152 95 61 87 200 ...

output:

23506
85 60201
263 85
186 263
884 186
384 884
998 384
174 998
875 174
334 875
518 334
738 518
125 738
257 125
799 257
1314 799
727 1314
1076 727
465 1076
1168 465
914 1168
930 914
509 930
318 509
780 318
75 780
99 75
1089 99
795 1089
393 795
1380 393
1991 1380
172 1991
1042 172
327 1042
747 327
3093...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #17:

score: 2
Acceptable Answer
time: 63ms
memory: 15908kb

input:

201 400
1 1 1 1 1 1 1 1 1 1 1 1 1 263 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 246 1 1 1 1 1 1 1 1 1 1 1 1 1 1 107 1 1 1 1 1 1 1 1 57 1 1 1 1 1 1 1 224 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 90 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

77869
40202 80401
80201 40202
43346 80201
80000 43346
80202 80000
78392 80202
78793 78392
79598 78793
79799 79598
78393 79799
79599 78393
80203 79599
77990 80203
78794 77990
80205 78794
79196 80205
79800 79196
77991 79800
78394 77991
80206 78394
79397 80206
77992 79397
80207 77992
77588 80207
78795 ...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #18:

score: 2
Acceptable Answer
time: 35ms
memory: 13768kb

input:

400 300
75 26 289 176 131 196 124 8 230 157 247 265 13 2 210 141 17 200 187 83 21 22 118 144 232 26 284 75 48 30 132 32 65 34 72 36 73 286 164 40 41 261 65 270 221 12 139 48 49 143 91 39 17 258 275 56 151 194 282 55 228 266 296 64 22 232 67 142 69 152 10 102 109 45 75 49 283 112 78 283 81 236 169 22...

output:

43105
841 120001
1685 841
127 1685
850 127
354 850
2537 354
146 2537
563 146
2336 563
743 2336
890 743
1321 890
414 1321
505 414
118 505
221 118
1178 221
678 1178
2850 678
3966 2850
854 3966
275 854
235 275
2040 235
2220 2040
462 2220
2712 462
1447 2712
206 1447
150 206
76 150
2370 76
2569 2370
2038...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #19:

score: 2
Acceptable Answer
time: 86ms
memory: 18432kb

input:

333 399
1 1 1 1 1 1 1 28 1 1 1 1 1 1 161 1 17 1 1 1 1 262 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 43 1 1 1 1 1 70 1 1 1 142 1 1 1 1 1 1 1 1 1 1 1 1 70 1 1 1 1 1 1 278 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 245 1 1 1 1 1 1 33 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 106 1 1 1 1 268 1 1 1 172 1 1 1 1 1 312 1 286 1 1 1 1 ...

output:

114795
37298 132868
76562 37298
19929 76562
20563 19929
24629 20563
99221 24629
84398 99221
99272 84398
31428 99272
33339 31428
92960 33339
131204 92960
64801 131204
66992 64801
93361 66992
75339 93361
71684 75339
21937 71684
86952 21937
9672 86952
96678 9672
81366 96678
126247 81366
58726 126247
13...

result:

points 0.40 first subtask is correct but plan is wrong.

Test #20:

score: 2
Acceptable Answer
time: 42ms
memory: 14756kb

input:

400 400
100 35 353 385 317 228 7 148 113 165 11 306 209 89 21 166 17 2 19 249 27 305 377 22 3 353 38 28 29 96 191 32 33 309 35 308 100 176 152 40 176 42 43 86 45 46 96 48 396 381 218 246 53 54 334 159 243 360 294 60 33 62 185 64 65 66 191 121 351 107 10 343 367 74 75 201 77 247 79 134 304 92 42 126 ...

output:

55816
329 160001
2458 329
898 2458
299 898
642 299
293 642
280 293
41 280
392 41
328 392
3180 328
1583 3180
507 1583
3918 507
6217 3918
2622 6217
291 2622
675 291
4581 675
692 4581
1181 692
378 1181
373 378
1547 373
942 1547
5158 942
1596 5158
7166 1596
1185 7166
1080 1185
755 1080
1004 755
246 1004...

result:

points 0.40 first subtask is correct but plan is wrong.
English 繁體中文 简体中文

服务器时间: 2024-12-02 18:57:41 | 开源项目