QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116070#5280. Depot RearrangementLinshey#80 17ms12428kbC++141.9kb2023-06-28 08:52:032024-05-31 14:20:16

Judging History

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

  • [2024-05-31 14:20:16]
  • 评测
  • 测评结果:80
  • 用时:17ms
  • 内存:12428kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 08:52:03]
  • 提交

answer


#include <bits/stdc++.h>

using namespace std; const int maxn = 3e3 + 5, maxm = 2e5 + 5;

int N, M, len;

int a[maxm];

vector<int> G[maxn];

int ct[maxn];

int b[maxm], c;

void DFS(int u)
{
    while (G[u].size())
    {
        int v = G[u].back();
        G[u].pop_back();
        // cerr << u << ' ' << v << endl;
        DFS(v);
    }
    b[c++] = u;
}

pair<int, int> zu[maxm]; int tt;

inline void Swap(int x, int y)
{
    swap(a[x], a[y]);
    zu[++tt] = { x, y };
}

inline int find(int st, int j)
{
    st -= M;
    st = (st - 1) * M + 1;
    for (int i = 0; i < N; i++) if (a[st + i] == j) return st + i;
    assert(0);
}

int main()
{
    scanf("%d%d", &N, &M), len = N * M;
    for (int i = 1; i <= len; i++) scanf("%d", a + i);
    for (int i = 1, st = 1; i <= N; i++, st += M)
    {
        memset(ct, 0, sizeof ct);
        for (int j = 0; j < M; j++) ct[a[st + j]]++; //, cerr << a[st + j] << endl;
        for (int j = 1; j <= M; j++)
        {
            if (ct[j] == 0) G[j].push_back(i + M); //, cerr << j << ' ' << i + M << endl;
            else
            {
                for (int k = 1; k < ct[j]; k++) G[i + M].push_back(j); //, cerr << i + M << ' ' << j << endl;
            }
        }
    }
    // cerr << "!" << endl;
    for (int st = 1; st <= M; st++)
    {
        c = 0;
        DFS(st);
        // for (int j = 0; j < c; j++) cerr << b[j] << ' '; cerr << endl;
        c--;
        if (!c) continue;
        // assert(c % 2 == 0);
        // for (int j = 1; j <= c; j++) assert((b[j] > M) == (j % 2 == 1));
        int x = find(b[1], b[c]);
        Swap(x, len + 1);
        for (int i = 3; i < c; i += 2)
        {
            int y = find(b[i], b[i - 1]);
            Swap(y, x);
            x = y;
        }
        Swap(len + 1, x);
    }
    printf("%d\n", tt);
    for (int i = 1; i <= tt; i++) printf("%d %d\n", zu[i].first, zu[i].second);
    return 0;
}

詳細信息

Test #1:

score: 5
Accepted
time: 1ms
memory: 5840kb

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

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
1 21
9 1
2 9
13 2
6 13
14 6
3 14
17 3
7 17
18 7
11 18
19 11
21 19

result:

ok both subtasks are correct!

Test #3:

score: 5
Accepted
time: 1ms
memory: 5980kb

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
25 101
4 25
13 4
34 13
72 34
24 72
86 24
46 86
11 46
2 11
23 2
12 23
41 12
32 41
52 32
31 52
65 31
75 65
63 75
96 63
54 96
42 54
21 42
82 21
26 82
92 26
51 92
78 51
44 78
95 44
85 95
101 85

result:

ok both subtasks are correct!

Test #4:

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

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
811 1001
352 811
772 352
172 772
942 172
101 942
451 101
183 451
812 183
202 812
825 202
665 825
844 665
733 844
711 733
1001 711
746 1001
706 746
1001 706

result:

ok both subtasks are correct!

Test #5:

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

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:

195
16301 20001
13107 16301
6807 13107
5914 6807
18114 5914
4140 18114
3785 4140
4216 3785
11233 4216
8933 11233
5833 8933
3716 5833
12204 3716
1413 12204
14213 1413
9005 14213
14205 9005
3010 14205
12210 3010
10304 12210
7804 10304
4904 7804
3635 4904
3917 3635
3317 3917
5017 3317
17817 5017
404 17...

result:

ok both subtasks are correct!

Test #6:

score: 5
Accepted
time: 1ms
memory: 6056kb

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
72 4021
25 72
3 25
83 3
42 83
35 42
7 35
48 7
166 48
22 166
9 22
26 9
249 26
85 249
356 85
203 356
101 203
328 101
104 328
143 104
415 143
93 415
169 93
65 169
184 65
367 184
82 367
73 82
97 73
498 97
46 498
23 46
167 23
1 167
138 1
144 138
123 144
45 123
308 45
354 308
431 354
124 431
187 124
...

result:

ok both subtasks are correct!

Test #7:

score: 5
Accepted
time: 5ms
memory: 4304kb

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:

205
73502 90001
26249 73502
16718 26249
30072 16718
15407 30072
49635 15407
15435 49635
5789 15435
16204 5789
22204 16204
80115 22204
22215 80115
88504 22215
19866 88504
81964 19866
19864 81964
79950 19864
66319 79950
81319 66319
83119 81319
68192 83119
51905 68192
75605 51905
36905 75605
87605 3690...

result:

ok both subtasks are correct!

Test #8:

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

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
1 12041
321 1
41 321
361 41
81 361
401 81
121 401
441 121
161 441
481 161
201 481
521 201
241 521
561 241
2 561
641 2
601 641
42 601
642 42
82 642
681 82
122 681
721 122
162 721
761 162
202 761
801 202
242 801
841 242
281 841
682 281
322 682
722 322
362 722
762 362
402 762
802 402
442 802
842 ...

result:

ok both subtasks are correct!

Test #9:

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

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
1518 40001
220 1518
153 220
19 153
149 19
242 149
9 242
484 9
731 484
1118 731
327 1118
410 327
52 410
550 52
1346 550
337 1346
112 337
1 112
422 1
1622 422
1083 1622
637 1083
1770 637
2152 1770
743 2152
1932 743
567 1932
135 567
878 135
404 878
5 404
473 5
2238 473
345 2238
2934 345
2618 2934...

result:

ok both subtasks are correct!

Test #10:

score: 0
Runtime Error

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:


result:


Test #11:

score: 5
Accepted
time: 5ms
memory: 5984kb

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
129 40001
362 129
136 362
733 136
527 733
456 527
930 456
228 930
128 228
1146 128
6 1146
432 6
1346 432
550 1346
1026 550
501 1026
334 501
284 334
1803 284
816 1803
1615 816
858 1615
353 858
590 353
293 590
1831 293
1918 1831
1248 1918
374 1248
221 374
2110 221
4 2110
307 4
103 307
319 103
26...

result:

ok both subtasks are correct!

Test #12:

score: 5
Accepted
time: 2ms
memory: 4600kb

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
2 6021
321 2
22 321
342 22
41 342
361 41
62 361
382 62
81 382
401 81
121 401
421 121
142 421
441 142
161 441
481 161
202 481
501 202
241 501
523 241
261 523
542 261
282 542
601 282
3 601
621 3
23 621
641 23
42 641
661 42
63 661
722 63
82 722
741 82
101 741
762 101
123 762
783 123
143 783
801 14...

result:

ok both subtasks are correct!

Test #13:

score: 5
Accepted
time: 13ms
memory: 9640kb

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
1887 90001
618 1887
72 618
1514 72
302 1514
2507 302
152 2507
1549 152
3017 1549
712 3017
931 712
10 931
1804 10
3029 1804
974 3029
5404 974
1376 5404
53 1376
1223 53
393 1223
657 393
1590 657
2424 1590
6090 2424
3426 6090
127 3426
614 127
24 614
942 24
1226 942
1539 1226
1896 1539
467 1896
22...

result:

ok both subtasks are correct!

Test #14:

score: 0
Runtime Error

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:


result:


Test #15:

score: 5
Accepted
time: 8ms
memory: 4600kb

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:

217
158401 160001
25065 158401
16253 25065
20427 16253
128041 20427
24041 128041
132548 24041
5524 132548
94724 5524
80942 94724
115342 80942
30174 115342
127374 30174
6974 127374
128491 6974
11555 128491
34895 11555
11295 34895
54083 11295
10483 54083
86017 10483
10417 86017
128755 10417
6891 12875...

result:

ok both subtasks are correct!

Test #16:

score: 5
Accepted
time: 9ms
memory: 7168kb

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
217 60201
617 217
220 617
1226 220
11 1226
2818 11
432 2818
1234 432
402 1234
1651 402
1890 1651
1253 1890
2277 1253
3347 2277
13 3347
1808 13
621 1808
4848 621
2027 4848
5205 2027
16 5205
2434 16
419 2434
6214 419
2689 6214
458 2689
3022 458
467 3022
2906 467
633 2906
3027 633
6408 3027
232 6...

result:

ok both subtasks are correct!

Test #17:

score: 0
Runtime Error

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:


result:


Test #18:

score: 5
Accepted
time: 17ms
memory: 11380kb

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
2438 120001
1208 2438
14 1208
304 14
1505 304
392 1505
685 392
223 685
692 223
355 692
3007 355
1204 3007
4063 1204
604 4063
3909 604
1206 3909
594 1206
4503 594
745 4503
1512 745
4508 1512
161 4508
2101 161
5115 2101
3706 5115
5402 3706
1216 5402
310 1216
4201 310
5553 4201
932 5553
4803 932
...

result:

ok both subtasks are correct!

Test #19:

score: 0
Runtime Error

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:


result:


Test #20:

score: 5
Accepted
time: 15ms
memory: 12428kb

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
2001 160001
405 2001
1222 405
523 1222
18 523
1642 18
147 1642
406 147
801 406
1481 801
1606 1481
2007 1606
4227 2007
2401 4227
5201 2401
2801 5201
11202 2801
3817 11202
802 3817
473 802
813 473
25 813
2813 25
7 2813
1566 7
3090 1566
2008 3090
1611 2008
11692 1611
4609 11692
13311 4609
4801 13...

result:

ok both subtasks are correct!