# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41876 | 2018-02-22T03:36:18 Z | funcsr | Sorting (IOI15_sorting) | C++14 | 14 ms | 10084 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[]) { // 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, M) { swap(S[X[i]], S[Y[i]]); //rep(i, N) cout<<S[i]<<",";cout<<"\n"; for (int t : G[i]) ps.pb(t); vector<int> nps; for (int x : ps) if (S[x] != x) nps.pb(x); swap(ps, nps); if (ps.empty()) { P[i] = Q[i] = 0; continue; } //cout<<"ps:{";for (int x :ps)cout<<x<<",";cout<<"}\n"; bool ok = false; rep(i, ps.size()) rep(j, i) { if (ok) break; int x = ps[i], y = ps[j]; if (S[x] == y && x == S[y]) { ok = true; //cout<<x<<"<->"<<y<<"\n"; 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; //cout<<x<<"<->"<<y<<"\n"; swap(S[x], S[y]); P[i] = x, Q[i] = y; } if (is_sorted(S, S+N)) { M = i+1; break; } //cout<<"->"; rep(i, N) cout<<S[i]<<",";cout<<"\n"; } rep(i, N) assert(S[i] == i); assert(ps.empty()); return M; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 5120 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 5120 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 5120 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 14 ms | 10084 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 | 14 ms | 10084 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |