QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #125888 | #5280. Depot Rearrangement | dengtingyu | 100 ✓ | 17ms | 30992kb | C++14 | 1.5kb | 2023-07-17 21:05:14 | 2023-07-17 21:05:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 810
ll n,m;
ll a[N];
vector<ll>t[N];
ll fir[N],v[N*N],nxt[N*N],w[N*N];ll cnt=0;
inline void add(ll x,ll y,ll z){
v[++cnt]=y;w[cnt]=z;nxt[cnt]=fir[x];fir[x]=cnt;
return ;
}
bool vis[N];
ll xu[N*N],cn=0;
inline void dfs(ll x){
vis[x]=1;
for(;fir[x];){
ll o=v[fir[x]];ll p=fir[x];
fir[x]=nxt[fir[x]];dfs(o);
xu[++cn]=p;
}return ;
}
ll x[N*N],y[N*N],cnn=0;
ll tt[N*N];ll ji=0;
ll jit[N];
int main()
{
// freopen("test1.in","r",stdin);
//freopen(".in","r",stdin);
// freopen("test1.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;ll g=n*m+1;for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)t[j].clear();
for(int j=1;j<=m;j++){
cin>>a[j];tt[++ji]=a[j];t[a[j]].push_back(j);
}for(int j=1;j<=m;j++){
if(t[j].empty()){
add(j+n,i,0);continue;
}for(int k=1;k<t[j].size();k++)add(i,j+n,t[j][k]+(i-1)*m);
}
}for(int i=1;i<=n;i++){
if(vis[i])continue;
cn=0;dfs(i);if(!cn)continue;
reverse(xu+1,xu+cn+1);
assert(v[xu[cn]]==i);
reverse(xu+1,xu+cn);
x[++cnn]=w[xu[1]];y[cnn]=g;
for(int i=3;i<=cn;i+=2){
x[++cnn]=w[xu[i-2]];y[cnn]=w[xu[i]];
}x[++cnn]=g;y[cnn]=w[xu[cn-1]];
}cout<<cnn<<'\n';
for(int i=1;i<=cnn;i++){
cout<<x[i]<<' '<<y[i]<<'\n';swap(tt[x[i]],tt[y[i]]);
}for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
jit[tt[(i-1)*m+j]]++;
}for(int j=1;j<=m;j++){
if(jit[j]!=i){
cout<<1;
}
assert(jit[j]==i);
}
}
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 5576kb
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: 2ms
memory: 11684kb
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 10 21 10 2 2 14 14 7 7 15 15 3 3 18 18 8 8 19 19 12 12 20 20 4 21 4
result:
ok both subtasks are correct!
Test #3:
score: 5
Accepted
time: 2ms
memory: 11684kb
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 18 101 18 38 38 29 29 75 75 30 30 90 90 49 49 39 39 20 20 43 43 6 6 28 28 67 67 56 56 66 66 76 76 36 36 16 16 26 26 87 87 97 97 55 55 44 44 27 27 95 95 58 58 79 79 50 50 100 100 89 89 3 101 3
result:
ok both subtasks are correct!
Test #4:
score: 5
Accepted
time: 2ms
memory: 11712kb
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 453 1001 453 184 184 734 734 713 713 819 819 359 359 775 775 175 175 210 210 830 830 670 670 850 850 814 814 949 949 109 1001 109 747 1001 747 707 1001 707
result:
ok both subtasks are correct!
Test #5:
score: 5
Accepted
time: 3ms
memory: 11800kb
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 13073 20001 13073 12213 12213 10354 10354 8254 8254 16367 16367 13167 13167 6867 6867 5967 5967 7667 7667 2067 2067 16854 16854 7854 7854 4955 4955 3641 3641 3971 3971 3334 3334 5034 5034 17871 17871 459 459 1541 1541 17469 17469 1569 1569 10541 10541 8875 8875 475 475 12259 12259 1488 1488 5159...
result:
ok both subtasks are correct!
Test #6:
score: 5
Accepted
time: 3ms
memory: 11752kb
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 84 4021 84 53 53 37 37 80 80 93 93 258 258 29 29 4 4 60 60 169 169 211 211 104 104 331 331 107 107 358 358 34 34 18 18 40 40 12 12 140 140 144 144 416 416 98 98 171 171 70 70 187 187 380 380 88 88 78 78 100 100 499 499 55 55 28 28 178 178 155 155 129 129 47 47 313 313 357 357 436 436 130 130 19...
result:
ok both subtasks are correct!
Test #7:
score: 5
Accepted
time: 0ms
memory: 14428kb
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 72662 90001 72662 11820 11820 72720 72720 75733 75733 37143 37143 68130 68130 22642 22642 36376 36376 38476 38476 39588 39588 77388 77388 69294 69294 1916 1916 55164 55164 13556 13556 85710 85710 20910 20910 42644 42644 44971 44971 53371 53371 26373 26373 19174 19174 85356 85356 31656 31656 7668...
result:
ok both subtasks are correct!
Test #8:
score: 5
Accepted
time: 3ms
memory: 16568kb
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 322 12041 322 42 42 362 362 82 82 402 402 122 122 442 442 162 162 482 482 202 202 522 522 242 242 562 562 2 2 642 642 602 602 43 43 643 643 83 83 682 682 123 123 722 722 163 163 762 762 203 203 802 802 243 243 842 842 282 282 683 683 323 323 723 723 363 363 763 763 403 403 803 803 443 443 843 ...
result:
ok both subtasks are correct!
Test #9:
score: 5
Accepted
time: 7ms
memory: 12796kb
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 196 40001 196 242 242 172 172 96 96 489 489 743 743 1181 1181 1099 1099 249 249 1356 1356 337 337 57 57 600 600 480 480 97 97 482 482 1644 1644 345 345 163 163 1571 1571 639 639 1771 1771 2166 2166 761 761 1998 1998 571 571 139 139 2266 2266 381 381 2953 2953 2644 2644 783 783 287 287 158 158 ...
result:
ok both subtasks are correct!
Test #10:
score: 5
Accepted
time: 3ms
memory: 11772kb
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 338 6401 338 137 137 2009 2009 977 977 806 806 182 182 40 40 353 353 234 234 839 839 1034 1034 510 510 750 750 1119 1119 1428 1428 2105 2105 17 17 757 757 276 276 396 396 1025 1025 938 938 281 281 73 73 192 192 2805 2805 1640 1640 765 765 2337 2337 1581 1581 1804 1804 1560 1560 534 534 3288 328...
result:
ok both subtasks are correct!
Test #11:
score: 5
Accepted
time: 4ms
memory: 12788kb
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 495 40001 495 794 794 170 170 397 397 159 159 982 982 253 253 186 186 1183 1183 550 550 483 483 1362 1362 558 558 1097 1097 577 577 353 353 293 293 1825 1825 866 866 1618 1618 892 892 374 374 592 592 298 298 1860 1860 1970 1970 1265 1265 393 393 300 300 2159 2159 2041 2041 90 90 311 311 195 19...
result:
ok both subtasks are correct!
Test #12:
score: 5
Accepted
time: 2ms
memory: 11980kb
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 322 6021 322 23 23 343 343 42 42 362 362 63 63 383 383 82 82 402 402 123 123 423 423 143 143 445 445 162 162 482 482 203 203 502 502 242 242 524 524 262 262 544 544 283 283 602 602 3 3 622 622 25 25 642 642 44 44 665 665 64 64 723 723 84 84 742 742 102 102 763 763 124 124 784 784 144 144 802 80...
result:
ok both subtasks are correct!
Test #13:
score: 5
Accepted
time: 9ms
memory: 14284kb
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 1710 90001 1710 597 597 1962 1962 712 712 2525 2525 861 861 212 212 1590 1590 3254 3254 231 231 1896 1896 3211 3211 974 974 5432 5432 1014 1014 2491 2491 6099 6099 1458 1458 53 53 1243 1243 487 487 660 660 1651 1651 100 100 7588 7588 3504 3504 218 218 667 667 567 567 1094 1094 1244 1244 1673 1...
result:
ok both subtasks are correct!
Test #14:
score: 5
Accepted
time: 11ms
memory: 23600kb
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 404 80401 404 2 2 802 802 3 3 1602 1602 1203 1203 4 4 2002 2002 1204 1204 803 803 405 405 1603 1603 804 804 1604 1604 5 5 2402 2402 1205 1205 406 406 2003 2003 1197 1197 2004 2004 7 7 3202 3202 1206 1206 2005 2005 1605 1605 408 408 2404 2404 8 8 809 809 2405 2405 2006 2006 409 409 810 810 2802...
result:
ok both subtasks are correct!
Test #15:
score: 5
Accepted
time: 9ms
memory: 12912kb
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 118784 160001 118784 784 160001 784 11722 160001 11722 2922 2922 147572 147572 133420 133420 87336 87336 132109 132109 90155 90155 48288 48288 62732 62732 19769 19769 71849 71849 132724 132724 49916 49916 119484 119484 6527 6527 129727 129727 84927 84927 119327 119327 49884 49884 45116 45116 363...
result:
ok both subtasks are correct!
Test #16:
score: 5
Accepted
time: 0ms
memory: 13532kb
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 2980 60201 2980 220 220 621 621 232 232 1234 1234 563 563 1253 1253 419 419 1659 1659 1934 1934 1307 1307 2334 2334 3392 3392 13 13 1827 1827 633 633 4989 4989 2164 2164 5357 5357 16 16 2600 2600 458 458 6254 6254 2798 2798 467 467 3027 3027 507 507 2914 2914 637 637 3041 3041 6412 6412 246 24...
result:
ok both subtasks are correct!
Test #17:
score: 5
Accepted
time: 15ms
memory: 24448kb
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 802 80401 802 2 2 1202 1202 803 803 402 402 1203 1203 3 3 1604 1604 804 804 404 404 1605 1605 4 4 2002 2002 915 915 1606 1606 1204 1204 405 405 2003 2003 5 5 2402 2402 6 6 2802 2802 7 7 3202 3202 8 8 3602 3602 9 9 4002 4002 10 10 4402 4402 11 11 4802 4802 12 12 5202 5202 13 13 806 806 2004 200...
result:
ok both subtasks are correct!
Test #18:
score: 5
Accepted
time: 12ms
memory: 15160kb
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 392 120001 392 1692 1692 427 427 690 690 421 421 3291 3291 1496 1496 124 124 775 775 4136 4136 745 745 4124 4124 1404 1404 600 600 4679 4679 806 806 1656 1656 1216 1216 253 253 2642 2642 1436 1436 372 372 2215 2215 5160 5160 3713 3713 5553 5553 4322 4322 5682 5682 4607 4607 243 243 2370 2370 8...
result:
ok both subtasks are correct!
Test #19:
score: 5
Accepted
time: 17ms
memory: 30992kb
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 1199 132868 1199 800 800 401 401 1200 1200 404 404 2 2 1598 1598 405 405 1599 1599 801 801 1600 1600 1201 1201 3 3 1997 1997 406 406 1998 1998 802 802 2386 2386 1601 1601 4 4 2000 2000 5 5 2397 2397 407 407 2001 2001 1202 1202 3046 3046 408 408 2398 2398 803 803 2399 2399 1203 1203 2400 2400 ...
result:
ok both subtasks are correct!
Test #20:
score: 5
Accepted
time: 13ms
memory: 22384kb
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 2388 160001 2388 523 523 1228 1228 569 569 147 147 546 546 1984 1984 4380 4380 1074 1074 1540 1540 1901 1901 2332 2332 5423 5423 2632 2632 11280 11280 2953 2953 1162 1162 690 690 920 920 11751 11751 3820 3820 13326 13326 4724 4724 391 391 2968 2968 2064 2064 1914 1914 14091 14091 2676 2676 159...
result:
ok both subtasks are correct!