# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
544229 | 2022-04-01T12:41:05 Z | timreizin | Sorting (IOI15_sorting) | C++17 | 1 ms | 468 KB |
#include "sorting.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; bool check(int m, vector<int> s, vector<pair<int, int>> &swaps) { for_each(swaps.begin(), swaps.begin() + m, [&s](auto i){ swap(s[i.first], s[i.second]); }); int res = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] == i) continue; ++res; swap(s[i], s[s[i]]); } return res <= m; } int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) { vector<int> s(n); for (int i = 0; i < n; ++i) s[i] = S[i]; vector<pair<int, int>> swaps(m); for (int i = 0; i < m; ++i) { swaps[i].first = X[i]; swaps[i].second = Y[i]; } int l = 0, r = m; while (l < r) { int m = (l + r) >> 1; if (check(m, s, swaps)) r = m; else l = m + 1; } //l - res //cout << l; vector<int> finish = s; for_each(swaps.begin(), swaps.begin() + l, [&s = finish](auto i){ swap(s[i.first], s[i.second]); }); vector<int> pos(n); for (int i = 0; i < n; ++i) pos[s[i]] = i; for (int i = 0, j = 0; j < l; ++i) { if (i == n) { P[l - 1] = 0; Q[l - 1] = 0; break; } //if in the end and j != l add (0, 0) if (finish[i] == i) continue; swap(pos[s[swaps[j].first]], pos[s[swaps[j].second]]); swap(s[swaps[j].first], s[swaps[j].second]); //a = finish[i], b = finish[finish[i]] int a = finish[i]; int b = finish[a]; swap(finish[i], finish[a]); P[j] = pos[a]; Q[j] = pos[b]; swap(s[pos[a]], s[pos[b]]); swap(pos[a], pos[b]); ++j; } return l; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Incorrect | 0 ms | 296 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Incorrect | 0 ms | 296 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 340 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 300 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Incorrect | 0 ms | 296 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |