QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141430 | #5280. Depot Rearrangement | penguinman# | 5 | 0ms | 3872kb | C++17 | 4.3kb | 2023-08-17 12:13:35 | 2024-07-04 01:46:35 |
answer
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
struct union_find{
ll N;
vi par, sz;
union_find(ll n): N(n){
par.resize(N);
sz.resize(N,1);
rep(i,0,N) par[i] = i;
}
ll root(ll now){
if(par[now] == now) return now;
return par[now] = root(par[now]);
}
void merge(ll u, ll v){
u = root(u);
v = root(v);
if(u == v) return;
if(sz[u] > sz[v]) std::swap(u,v);
sz[v] += sz[u];
sz[u] = 0;
par[u] = v;
}
bool same(ll u, ll v){
return root(u) == root(v);
}
};
int main(){
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
ll N,M; cin >> N >> M;
vector<vii> data(N,vii(M));
vi A(N*M);
rep(i,0,N*M){
cin >> A[i];
A[i]--;
data[i/M][A[i]].pb(i);
}
vii edge(N+M), weight(N+M);
{
ll cnt = N*M;
rep(i,0,N){
rep(j,0,M){
if(data[i][j].size() == 0){
edge[j].pb(M+i);
weight[j].pb(cnt++);
}
else{
rep(k,1,data[i][j].size()){
edge[M+i].pb(j);
weight[M+i].pb(data[i][j][k]);
}
}
}
}
}
ll ans = 0;
{
vector<bool> flag(N+M);
rep(i,0,N+M){
if(edge[i].empty()) continue;
if(flag[i]) continue;
flag[i] = true;
std::queue<ll> que;
que.push(i);
ll sum = 0;
while(!que.empty()){
ll now = que.front();
que.pop();
sum += edge[now].size();
for(auto next: edge[now]){
if(flag[next]) continue;
flag[next] = true;
que.push(next);
}
}
sum /= 2;
ans += sum+1;
}
cout << ans << ln;
}
union_find tree(N*M*2);
vi nidx(N+M);
vi next(2*N*M, -1);
rep(i,0,N+M){
if(nidx[i] == edge[i].size()) continue;
ll now = i;
vi ord;
while(true){
if(nidx[now] == edge[now].size()) break;
ll next = edge[now][nidx[now]];
ll vert = weight[now][nidx[now]];
ord.pb(vert);
nidx[now]++;
now = next;
}
rep(j,0,ord.size()){
next[ord[j]] = ord[(j+1)%ord.size()];
tree.merge(ord[j], ord[0]);
}
}
rep(i,0,M+N){
rep(j,1,weight[i].size()){
ll n = weight[i][j-1];
ll m = weight[i][j];
if(tree.same(n,m)) continue;
tree.merge(n,m);
std::swap(next[n], next[m]);
}
}
ll cnt = 0;
A.pb(-1);
rep(i,0,2*N*M){
if(next[i] == -1) continue;
vi ord;
ll now = i;
while(true){
if(next[now] == -1) break;
if(now < N*M) ord.pb(now);
ll nex = next[now];
next[now] = -1;
now = nex;
}
ll n = ord.size();
reverse(all(ord));
cout << ord[n-1]+1 << " " << N*M+1 << ln;
assert(A[N*M] == -1);
std::swap(A[N*M], A[ord[n-1]]);
cnt++;
per(j,n-1,1){
cout << ord[j-1]+1 << " " << ord[j]+1 << ln;
assert(A[ord[j]] == -1);
std::swap(A[ord[j]], A[ord[j-1]]);
cnt++;
}
cout << N*M+1 << " " << ord[0]+1 << ln;
assert(A[ord[0]] == -1);
std::swap(A[ord[0]], A[N*M]);
cnt++;
}
assert(cnt == ans);
rep(i,0,N){
vi cnt(M);
rep(j,i*M,i*M+M) cnt[A[j]]++;
rep(j,0,M) assert(cnt[j] == 1);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 3872kb
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: 0
Runtime Error
input:
5 4 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4
output:
result:
Test #3:
score: 0
Runtime Error
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:
result:
Test #4:
score: 0
Runtime Error
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:
result:
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: 0
Runtime Error
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 4 4021 29 4 80 29 93 80 258 93 104 258 211 104 169 211 60 169 18 60 34 18 358 34 140 358 12 140 40 12 11 40 171 11 98 171 416 98 107 416 331 107 144 331 178 144 28 178 55 28 499 55 88 499 380 88 180 380 155 180 187 155 70 187 193 70 129 193 210 129 78 210 100 78 194 100 217 194 231 217 219 231 ...
result:
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: 0
Runtime Error
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 2 12041 362 2 42 362 402 42 82 402 442 82 122 442 482 122 162 482 522 162 202 522 562 202 242 562 602 242 683 602 323 683 723 323 363 723 763 363 403 763 803 403 443 803 843 443 483 843 883 483 523 883 923 523 324 923 963 324 364 963 1003 364 404 1003 1043 404 444 1043 1083 444 484 1083 1123 4...
result:
Test #9:
score: 0
Runtime Error
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 7 40001 2441 7 796 2441 1275 796 2187 1275 1488 2187 1792 1488 996 1792 794 996 2147 794 737 2147 31 737 2584 31 5784 2584 6491 5784 10066 6491 7280 10066 7938 7280 6960 7938 4448 6960 5274 4448 10180 5274 6008 10180 4098 6008 1522 4098 4488 1522 5372 4488 5289 5372 5396 5289 5858 5396 6468 58...
result:
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:
1316 17 6401 2105 17 1428 2105 1119 1428 750 1119 510 750 3288 510 534 3288 1581 534 2337 1581 276 2337 757 276 73 757 281 73 938 281 1025 938 396 1025 192 396 155 192 2417 155 3453 2417 245 3453 1366 245 861 1366 1560 861 1804 1560 2065 1804 2506 2065 1268 2506 1869 1268 189 1869 765 189 1640 765 2...
result:
Test #11:
score: 0
Runtime Error
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 9 40001 1564 9 1829 1564 2674 1829 2859 2674 966 2859 2468 966 1964 2468 1513 1964 983 1513 2569 983 589 2569 1272 589 1670 1272 3066 1670 2333 3066 1341 2333 2766 1341 3800 2766 4927 3800 3036 4927 3542 3036 3931 3542 5090 3931 4099 5090 5397 4099 1996 5397 372 1996 469 372 1798 469 161 1798 ...
result:
Test #12:
score: 0
Runtime Error
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 3 6021 343 3 23 343 362 23 42 362 383 42 63 383 402 63 82 402 423 82 123 423 445 123 143 445 482 143 162 482 502 162 203 502 524 203 242 524 544 242 262 544 602 262 283 602 622 283 4 622 642 4 25 642 665 25 44 665 723 44 64 723 742 64 84 742 763 84 102 763 784 102 124 784 802 124 144 802 845 14...
result:
Test #13:
score: 0
Runtime Error
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 15 90001 1420 15 8666 1420 27860 8666 42483 27860 38630 42483 61858 38630 57457 61858 49491 57457 44987 49491 26872 44987 47044 26872 57530 47044 49771 57530 62871 49771 63265 62871 66200 63265 71928 66200 72612 71928 70732 72612 67668 70732 61954 67668 59374 61954 64884 59374 72257 64884 8278...
result:
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:
63990 2 80401 802 2 3 802 1203 3 1602 1203 4 1602 1603 4 405 1603 803 405 1204 803 2002 1204 5 2002 2003 5 406 2003 1205 406 2402 1205 7 2402 2404 7 408 2404 1604 408 804 1604 1605 804 2004 1605 1197 2004 2005 1197 1206 2005 3202 1206 8 3202 2802 8 809 2802 9 809 3203 9 409 3203 2006 409 2405 2006 8...
result:
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: 0
Runtime Error
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 13 60201 3392 13 1253 3392 563 1253 4989 563 633 4989 419 633 1659 419 1307 1659 1934 1307 2334 1934 1827 2334 16 1827 5357 16 2164 5357 6254 2164 458 6254 2600 458 25 2600 6412 25 2914 6412 467 2914 2798 467 6916 2798 246 6916 7184 246 3027 7184 507 3027 3041 507 637 3041 3956 637 7976 3956 4...
result:
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:
77869 2 80401 1202 2 3 1202 1604 3 4 1604 2002 4 5 2002 2402 5 6 2402 2802 6 7 2802 3202 7 8 3202 3602 8 9 3602 4002 9 10 4002 4402 10 11 4402 4802 11 12 4802 5202 12 13 5202 5981 13 402 5981 1223 402 6405 1223 1224 6405 6805 1224 1225 6805 7205 1225 1226 7205 7605 1226 1227 7605 8005 1227 1620 8005...
result:
Test #18:
score: 0
Runtime Error
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 26 120001 1321 26 1171 1321 129 1171 1732 129 1349 1732 385 1349 2842 385 1179 2842 2599 1179 5643 2599 9238 5643 12772 9238 11429 12772 22938 11429 19298 22938 8962 19298 6122 8962 24772 6122 19727 24772 10001 19727 11228 10001 5172 11228 12237 5172 7865 12237 27195 7865 11044 27195 200 11044...
result:
Test #19:
score: 0
Runtime Error
input:
output:
result:
Test #20:
score: 0
Judgement Failed