# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
379608 | 2021-03-18T20:05:32 Z | idk321 | Sorting (IOI15_sorting) | C++11 | 6 ms | 620 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 600005; int n, m; int* s; int* x; int* y; int* q; int* p; int np[N]; int nq[N]; bool isOk(int r) { for (int i = 0; i < m; i++) { p[i] = 0; q[i] = 0; } vector<int> change(n); for (int i = 0; i < n; i++) change[i] = i; for (int i = 0; i <= r; i++) { swap(change[x[i]], change[y[i]]); } vector<int> needed(n); for (int i = 0; i < n; i++) { needed[change[i]] = i; } vector<int> cur(s, s + n); vector<int> isOn(n); for (int i = 0; i < n; i++) { isOn[cur[i]] = i; } int check = 0; for (int i = 0; i <= r; i++) { swap(cur[x[i]], cur[y[i]]); swap(needed[x[i]], needed[y[i]]); isOn[cur[x[i]]] = x[i]; isOn[cur[y[i]]] = y[i]; while (check < n) { if (check != needed[isOn[check]]) { int a = isOn[check]; int b = isOn[needed[isOn[check]]]; swap(cur[a], cur[b]); isOn[cur[a]] = a; isOn[cur[b]] = b; np[i] = a; nq[i] = b; break; } check++; } if (check == n) { np[i] = 0; nq[i] = 0; } } cout << r << endl; for (int i : cur) cout << i << " "; cout << endl; for (int i = 1; i < n; i++) { if (cur[i] < cur[i - 1]) return false; } return true; } int bs() { int a = 0; int b = m - 1; int res = -1; while (a <= b) { int mid = (a + b) / 2; if (isOk(mid)) { res = mid; b = mid - 1; } else { a = mid + 1; } } return res; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; s = S; x = X; y = Y; p = P; q = Q; bool alreadyGood = true; for (int i = 1; i < n; i++) { if (s[i] < s[i - 1]) alreadyGood = false; } if (alreadyGood) return 0; int best = bs() + 1; for (int i = 0; i < best; i++) { p[i] = np[i]; q[i] = nq[i]; } return best; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Incorrect | 0 ms | 364 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Incorrect | 0 ms | 364 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Incorrect | 1 ms | 364 KB | Expected EOLN |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Incorrect | 0 ms | 364 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 620 KB | Expected EOLN |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 620 KB | Expected EOLN |
2 | Halted | 0 ms | 0 KB | - |