QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116070 | #5280. Depot Rearrangement | Linshey# | 80 | 17ms | 12428kb | C++14 | 1.9kb | 2023-06-28 08:52:03 | 2024-05-31 14:20:16 |
Judging History
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!