# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
474196 | 2021-09-17T10:09:17 Z | jwvg0425 | Sorting (IOI15_sorting) | C++17 | 110 ms | 568 KB |
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #include "sorting.h" #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; template<typename T, typename Pr = less<T>> using pq = priority_queue<T, vector<T>, Pr>; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; bool sorted(vector<int> s) { for (int i = 0; i < s.size(); i++) if (s[i] != i) return false; return true; } vector<ii> solve(vector<int> s, vector<ii> r) { int n = s.size(); int m = r.size(); vector<ii> res; for (int i = 0; i < m && !sorted(s); i++) { vector<int> rev(n), idx(n); swap(s[r[i].xx], s[r[i].yy]); for (int j = 0; j < n; j++) rev[j] = j; for (int j = i + 1; j < m; j++) swap(rev[r[j].xx], rev[r[j].yy]); for (int j = 0; j < n; j++) idx[rev[j]] = j; // s[i] -> idx[i] bool f = false; for (int x = 0; x < n; x++) { if (s[x] == idx[x]) continue; int j = find(all(s), idx[x]) - s.begin(); res.emplace_back(x, j); swap(s[x], s[j]); f = true; break; } if (!f) res.emplace_back(0, 0); } assert(sorted(s)); return res; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<int> s(N); vector<ii> r(M); for (int i = 0; i < N; i++) s[i] = S[i]; for (int i = 0; i < M; i++) { r[i].xx = X[i]; r[i].yy = Y[i]; } auto res = solve(s, r); for (int i = 0; i < res.size(); i++) { P[i] = res[i].xx; Q[i] = res[i].yy; } return res.size(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 300 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 2 ms | 332 KB | Output is correct |
11 | Correct | 2 ms | 332 KB | Output is correct |
12 | Correct | 2 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Incorrect | 2 ms | 332 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 0 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 300 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 2 ms | 332 KB | Output is correct |
11 | Correct | 2 ms | 332 KB | Output is correct |
12 | Correct | 2 ms | 332 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Incorrect | 2 ms | 332 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 110 ms | 568 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 110 ms | 568 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |