# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
170911 | 2019-12-26T17:04:08 Z | socho | Sorting (IOI15_sorting) | C++14 | 53 ms | 604 KB |
#include "sorting.h" #include "bits/stdc++.h" using namespace std; const int MXN = 200005; int n, m; int seq[MXN]; vector<pair<int, int> > plan; vector<pair<int, int> > ans; bool works(int sw) { // cout << "try: " << sw << ' '; ans.clear(); int nsw[n]; for (int i=0; i<n; i++) nsw[i] = seq[i]; int where[n]; for (int i=0; i<sw; i++) { int a = plan[i].first, b = plan[i].second; swap(nsw[a], nsw[b]); } for (int i=0; i<n; i++) { where[nsw[i]] = i; } int need = 0; for (int i=0; i<n; i++) { if (nsw[i] == i) continue; need++; int ati = nsw[i]; int whei = where[i]; where[ati] = whei; where[i] = i; nsw[i] = i; nsw[whei] = ati; ans.push_back(make_pair(i, whei)); } // cout << (need <= sw) << endl; // if (sw == 3) return true; return need <= sw; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; for (int i=0; i<n; i++) seq[i] = S[i]; for (int i=0; i<m; i++) { plan.push_back(make_pair(X[i], Y[i])); } for (int j=0; j<=M; j++) { if (works(j)) { for (int i=0; i<j; i++) { P[i] = ans[i].first; Q[i] = ans[i].second; } return j; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Incorrect | 2 ms | 376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 256 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 376 KB | Output is correct |
14 | Incorrect | 2 ms | 376 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 53 ms | 604 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 53 ms | 604 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |