# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

387262 | 2021-04-08T07:47:08 Z | ParsaAlizadeh | Sorting (IOI15_sorting) | C++17 | 204 ms | 22600 KB |

#include <bits/stdc++.h> #include "sorting.h" using namespace std; typedef pair<int, int> pii; vector<int> perm; vector<pii> alice, bob; bool check(int t) { vector<int> tmp(perm); for (int i = 0; i < t; i++) { swap(tmp[alice[i].first], tmp[alice[i].second]); } bob.clear(); for (int i = 0; i < tmp.size(); i++) { while (tmp[i] != i) { bob.emplace_back(tmp[i], tmp[tmp[i]]); swap(tmp[i], tmp[tmp[i]]); } } while (bob.size() < t) bob.emplace_back(0, 0); return bob.size() == t; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { perm.assign(S, S + N); for (int i = 0; i < M; i++) { alice.emplace_back(X[i], Y[i]); } int L = -1, R = M; while (R - L > 1) { int mid = (L + R) >> 1; (check(mid) ? R : L) = mid; } check(R); vector<int> inv(N); for (int i = 0; i < N; i++) { inv[perm[i]] = i; } const auto replc = [&] (int i, int j) { swap(perm[i], perm[j]); inv[perm[i]] = i; inv[perm[j]] = j; }; for (int i = 0; i < R; i++) { replc(X[i], Y[i]); P[i] = inv[bob[i].first]; Q[i] = inv[bob[i].second]; replc(P[i], Q[i]); } return R; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 364 KB | Output is correct |

2 | Correct | 1 ms | 364 KB | Output is correct |

3 | Correct | 1 ms | 364 KB | Output is correct |

4 | Correct | 1 ms | 364 KB | Output is correct |

5 | Correct | 1 ms | 364 KB | Output is correct |

6 | Correct | 1 ms | 364 KB | Output is correct |

7 | Correct | 1 ms | 364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 364 KB | Output is correct |

2 | Correct | 1 ms | 364 KB | Output is correct |

3 | Correct | 1 ms | 364 KB | Output is correct |

4 | Correct | 1 ms | 364 KB | Output is correct |

5 | Correct | 1 ms | 364 KB | Output is correct |

6 | Correct | 1 ms | 364 KB | Output is correct |

7 | Correct | 1 ms | 364 KB | Output is correct |

8 | Correct | 1 ms | 364 KB | Output is correct |

9 | Correct | 1 ms | 364 KB | Output is correct |

10 | Correct | 1 ms | 364 KB | Output is correct |

11 | Correct | 1 ms | 364 KB | Output is correct |

12 | Correct | 1 ms | 364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 364 KB | Output is correct |

2 | Correct | 1 ms | 364 KB | Output is correct |

3 | Correct | 1 ms | 364 KB | Output is correct |

4 | Correct | 1 ms | 364 KB | Output is correct |

5 | Correct | 1 ms | 364 KB | Output is correct |

6 | Correct | 1 ms | 364 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 364 KB | Output is correct |

2 | Correct | 1 ms | 364 KB | Output is correct |

3 | Correct | 1 ms | 364 KB | Output is correct |

4 | Correct | 1 ms | 364 KB | Output is correct |

5 | Correct | 1 ms | 364 KB | Output is correct |

6 | Correct | 1 ms | 364 KB | Output is correct |

7 | Correct | 1 ms | 364 KB | Output is correct |

8 | Correct | 1 ms | 364 KB | Output is correct |

9 | Correct | 1 ms | 364 KB | Output is correct |

10 | Correct | 1 ms | 364 KB | Output is correct |

11 | Correct | 1 ms | 364 KB | Output is correct |

12 | Correct | 1 ms | 364 KB | Output is correct |

13 | Correct | 1 ms | 364 KB | Output is correct |

14 | Correct | 1 ms | 364 KB | Output is correct |

15 | Correct | 1 ms | 364 KB | Output is correct |

16 | Correct | 1 ms | 364 KB | Output is correct |

17 | Correct | 1 ms | 364 KB | Output is correct |

18 | Correct | 1 ms | 364 KB | Output is correct |

19 | Correct | 1 ms | 364 KB | Output is correct |

20 | Correct | 1 ms | 364 KB | Output is correct |

21 | Correct | 2 ms | 632 KB | Output is correct |

22 | Correct | 2 ms | 748 KB | Output is correct |

23 | Correct | 2 ms | 748 KB | Output is correct |

24 | Correct | 2 ms | 748 KB | Output is correct |

25 | Correct | 2 ms | 748 KB | Output is correct |

26 | Correct | 2 ms | 748 KB | Output is correct |

27 | Correct | 2 ms | 636 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 492 KB | Output is correct |

2 | Correct | 2 ms | 492 KB | Output is correct |

3 | Correct | 2 ms | 492 KB | Output is correct |

4 | Correct | 1 ms | 492 KB | Output is correct |

5 | Correct | 2 ms | 492 KB | Output is correct |

6 | Correct | 2 ms | 492 KB | Output is correct |

7 | Correct | 2 ms | 492 KB | Output is correct |

8 | Correct | 2 ms | 492 KB | Output is correct |

9 | Correct | 2 ms | 600 KB | Output is correct |

10 | Correct | 3 ms | 492 KB | Output is correct |

11 | Correct | 2 ms | 600 KB | Output is correct |

12 | Correct | 2 ms | 492 KB | Output is correct |

13 | Correct | 2 ms | 492 KB | Output is correct |

14 | Correct | 2 ms | 492 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 2 ms | 492 KB | Output is correct |

2 | Correct | 2 ms | 492 KB | Output is correct |

3 | Correct | 2 ms | 492 KB | Output is correct |

4 | Correct | 1 ms | 492 KB | Output is correct |

5 | Correct | 2 ms | 492 KB | Output is correct |

6 | Correct | 2 ms | 492 KB | Output is correct |

7 | Correct | 2 ms | 492 KB | Output is correct |

8 | Correct | 2 ms | 492 KB | Output is correct |

9 | Correct | 2 ms | 600 KB | Output is correct |

10 | Correct | 3 ms | 492 KB | Output is correct |

11 | Correct | 2 ms | 600 KB | Output is correct |

12 | Correct | 2 ms | 492 KB | Output is correct |

13 | Correct | 2 ms | 492 KB | Output is correct |

14 | Correct | 2 ms | 492 KB | Output is correct |

15 | Correct | 166 ms | 19800 KB | Output is correct |

16 | Correct | 176 ms | 20168 KB | Output is correct |

17 | Correct | 204 ms | 21320 KB | Output is correct |

18 | Correct | 70 ms | 17364 KB | Output is correct |

19 | Correct | 135 ms | 20168 KB | Output is correct |

20 | Correct | 146 ms | 20552 KB | Output is correct |

21 | Correct | 149 ms | 20680 KB | Output is correct |

22 | Correct | 164 ms | 21192 KB | Output is correct |

23 | Correct | 183 ms | 21576 KB | Output is correct |

24 | Correct | 191 ms | 21576 KB | Output is correct |

25 | Correct | 193 ms | 21704 KB | Output is correct |

26 | Correct | 147 ms | 20552 KB | Output is correct |

27 | Correct | 124 ms | 19912 KB | Output is correct |

28 | Correct | 192 ms | 21320 KB | Output is correct |

29 | Correct | 185 ms | 21320 KB | Output is correct |

30 | Correct | 101 ms | 19400 KB | Output is correct |

31 | Correct | 188 ms | 21960 KB | Output is correct |

32 | Correct | 185 ms | 21064 KB | Output is correct |

33 | Correct | 197 ms | 21832 KB | Output is correct |

34 | Correct | 190 ms | 21576 KB | Output is correct |

35 | Correct | 134 ms | 19912 KB | Output is correct |

36 | Correct | 61 ms | 18516 KB | Output is correct |

37 | Correct | 200 ms | 22600 KB | Output is correct |

38 | Correct | 190 ms | 21576 KB | Output is correct |

39 | Correct | 192 ms | 22088 KB | Output is correct |