# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1040137 | 2024-07-31T17:01:26 Z | Zicrus | Sorting (IOI15_sorting) | C++17 | 1 ms | 348 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; typedef long long ll; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P1[], int Q1[]) { vector<ll> h(N); for (int i = 0; i < N; i++) h[i] = S[i]; ll ooo = 0; for (int i = 0; i < N; i++) { if (h[i] != i) ooo++; } if (ooo == 0) return 0; ll res1 =0; ll low = 1, high = N; while (low < high) { ll g = (low + high) / 2; vector<int> P(M), Q(M); ll res = 0; vector<ll> s = h; vector<ll> order = s; vector<ll> revOrd(N), revS(N); for (int j = 0; j < g; j++) { swap(order[X[j]], order[Y[j]]); } for (int i = 0; i < N; i++) { revOrd[order[i]] = i; revS[s[i]] = i; } for (int i = 0; i < g; i++) { swap(s[X[i]], s[Y[i]]); swap(revS[s[X[i]]], revS[s[Y[i]]]); int firstOut = -1, id = -1; for (int j = 0; j < N; j++) { if (order[j] != j) { firstOut = order[id = j]; break; } } if (firstOut == -1) { P[res] = Q[res] = 0; res++; } else { ll iter = revOrd[id]; ll v = order[iter]; ll id1 = revS[firstOut]; ll id2 = revS[v]; swap(s[id1], s[id2]); swap(revS[s[id1]], revS[s[id2]]); swap(order[iter], order[id]); swap(revOrd[order[iter]], revOrd[order[id]]); P[res] = id1; Q[res] = id2; res++; } for (int j = 0; j < N; j++) { if (s[j] != j) continue; } break; } ll ooo = 0; for (int i = 0; i < N; i++) { if (s[i] != i) ooo++; } if (ooo == 0) { res1 = res; high = g; for (int i = 0; i < res; i++) { P1[i] = P[i]; Q1[i] = Q[i]; } } else { low = g+1; } } return res1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Incorrect | 0 ms | 348 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Incorrect | 0 ms | 348 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |