# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41880 | 2018-02-22T03:48:24 Z | funcsr | Sorting (IOI15_sorting) | C++14 | 370 ms | 10360 KB |
#include "sorting.h" #include <vector> #include <iostream> #include <algorithm> #include <queue> #include <cassert> using namespace std; #define rep(i, n) for (int i=0; i<(n); i++) #define pb push_back #define _1 first #define _2 second #define INF 1145141919 #define MOD 1000000007 bool used[200000]; vector<int> G[200000]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { if (is_sorted(S, S+N)) return 0; // subtask 1-4 rep(i, N) used[i] = false; for (int i=M-1; i>=0; i--) { if (X[i] == Y[i]) continue; if (!used[X[i]]) { G[i].pb(X[i]); used[X[i]] = true; } if (!used[Y[i]]) { G[i].pb(Y[i]); used[Y[i]] = true; } } vector<int> ps; rep(i, N) if (!used[i] && S[i] != i) ps.pb(i); rep(i, M) { swap(S[X[i]], S[Y[i]]); //rep(i, N) cout<<S[i]<<",";cout<<"\n"; for (int t : G[i]) if (S[t] != t) ps.pb(t); if (ps.empty()) { P[i] = Q[i] = 0; } else { bool ok = false; rep(j, ps.size()) rep(k, j) { if (ok) break; int x = ps[j], y = ps[k]; if (S[x] == y && x == S[y]) { ok = true; swap(S[x], S[y]); P[i] = x, Q[i] = y; break; } } if (!ok) { int x = ps[0], y = -1; rep(i, N) if (S[i] == x) y = i; swap(S[x], S[y]); P[i] = x, Q[i] = y; } } vector<int> nps; for (int x : ps) if (S[x] != x) nps.pb(x); swap(ps, nps); if (is_sorted(S, S+N)) { M = i+1; break; } } rep(i, N) assert(S[i] == i); assert(ps.empty()); return M; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 6 ms | 4992 KB | Output is correct |
4 | Correct | 8 ms | 4992 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 8 ms | 4992 KB | Output is correct |
7 | Correct | 7 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 6 ms | 4992 KB | Output is correct |
4 | Correct | 8 ms | 4992 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 8 ms | 4992 KB | Output is correct |
7 | Correct | 7 ms | 4992 KB | Output is correct |
8 | Correct | 7 ms | 4992 KB | Output is correct |
9 | Correct | 6 ms | 4992 KB | Output is correct |
10 | Correct | 9 ms | 5120 KB | Output is correct |
11 | Correct | 7 ms | 5120 KB | Output is correct |
12 | Correct | 7 ms | 5120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 4992 KB | Output is correct |
3 | Correct | 7 ms | 4992 KB | Output is correct |
4 | Correct | 7 ms | 5120 KB | Output is correct |
5 | Correct | 8 ms | 5120 KB | Output is correct |
6 | Correct | 8 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 6 ms | 4992 KB | Output is correct |
4 | Correct | 8 ms | 4992 KB | Output is correct |
5 | Correct | 7 ms | 4992 KB | Output is correct |
6 | Correct | 8 ms | 4992 KB | Output is correct |
7 | Correct | 7 ms | 4992 KB | Output is correct |
8 | Correct | 7 ms | 4992 KB | Output is correct |
9 | Correct | 6 ms | 4992 KB | Output is correct |
10 | Correct | 9 ms | 5120 KB | Output is correct |
11 | Correct | 7 ms | 5120 KB | Output is correct |
12 | Correct | 7 ms | 5120 KB | Output is correct |
13 | Correct | 6 ms | 4992 KB | Output is correct |
14 | Correct | 7 ms | 4992 KB | Output is correct |
15 | Correct | 7 ms | 4992 KB | Output is correct |
16 | Correct | 7 ms | 5120 KB | Output is correct |
17 | Correct | 8 ms | 5120 KB | Output is correct |
18 | Correct | 8 ms | 4992 KB | Output is correct |
19 | Correct | 6 ms | 4992 KB | Output is correct |
20 | Correct | 7 ms | 4992 KB | Output is correct |
21 | Runtime error | 17 ms | 10360 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 370 ms | 10280 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 370 ms | 10280 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |