# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
299474 | 2020-09-15T02:20:16 Z | Hideo | Sorting (IOI15_sorting) | C++17 | 209 ms | 19884 KB |
#include "sorting.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(s) s.begin(), s.end() #define pb push_back #define fr first #define sc second #define vi vector < int > #define pi pair < int, int > const int MN = 3e5 + 7; vector < pi > sw, out; int a[MN], b[MN], r[MN]; int x[MN], y[MN]; int n, m; bool check (int k){ for (int i = 0; i < n; i++) a[i] = b[i]; for (int i = 0; i < k; i++) swap(a[x[i]], a[y[i]]); for (int i = 0; i < n; i++) r[a[i]] = i; vector < pi > kek; for (int i = 0; i < n; i++){ int it = i; while (it != a[it]){ int x = it, y = a[it]; it = a[it]; kek.pb({x, y}); swap(a[r[x]], a[r[y]]); swap(r[x], r[y]); } } if (kek.size() <= k) sw = kek; return kek.size() <= k; } void simulate (int k){ while (sw.size() != k) sw.pb({0, 0}); for (int i = 0; i < n; i++){ a[i] = b[i]; r[a[i]] = i; } for (int i = 0; i < k; i++){ swap(a[x[i]], a[y[i]]); swap(r[a[x[i]]], r[a[y[i]]]); int v = r[sw[i].fr], u = r[sw[i].sc]; out.pb({v, u}); swap(a[v], a[u]); swap(r[a[v]], r[a[u]]); } } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; bool sorted = true; for (int i = 0; i < n; i++){ b[i] = S[i]; if (b[i] != i) sorted = false; } if (sorted) return 0; for (int i = 0; i < m; i++){ x[i] = X[i]; y[i] = Y[i]; } int lf = 0, rg = M + 1; while (lf + 1 < rg){ int mid = (lf + rg) >> 1; if (check(mid)) rg = mid; else lf = mid; } simulate(rg); for (int i = 0; i < out.size(); i++){ P[i] = out[i].fr; Q[i] = out[i].sc; } return rg; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 0 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 1 ms | 384 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 1 ms | 384 KB | Output is correct |
21 | Correct | 2 ms | 640 KB | Output is correct |
22 | Correct | 1 ms | 640 KB | Output is correct |
23 | Correct | 2 ms | 640 KB | Output is correct |
24 | Correct | 1 ms | 640 KB | Output is correct |
25 | Correct | 1 ms | 640 KB | Output is correct |
26 | Correct | 1 ms | 640 KB | Output is correct |
27 | Correct | 2 ms | 640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 640 KB | Output is correct |
14 | Correct | 1 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 512 KB | Output is correct |
4 | Correct | 1 ms | 512 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 2 ms | 512 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 512 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 512 KB | Output is correct |
13 | Correct | 2 ms | 640 KB | Output is correct |
14 | Correct | 1 ms | 512 KB | Output is correct |
15 | Incorrect | 209 ms | 19884 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |