# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
293982 | 2020-09-08T14:15:22 Z | arayi | Sorting (IOI15_sorting) | C++17 | 3 ms | 512 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; const int N = 2e5 + 30; int n, m; int a[N], ind[N], b[N], x[N], y[N]; int col[N]; void dfs(int v) { col[v] = 1; if(!col[b[v]]) dfs(b[v]); } int cnt() { int ret = 0; for (int i = 0; i < n; i++) if(!col[i]) ret++, dfs(i); for (int i = 0; i < n; i++) col[i] = 0; return n - ret; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; for (int i = 0; i < n; i++) a[i] = S[i], ind[a[i]] = i; for (int i = 0; i < M; i++) x[i] = X[i], y[i] = Y[i]; int l = 0, r = M, ans = M; while(l <= r) { int mid = (l + r) / 2; for (int i = 0; i < n; i++) b[i] = a[i]; for (int i = 0; i < mid; i++) swap(b[x[i]], b[y[i]]); int sm = cnt(); if(sm <= mid) ans = mid, r = mid - 1; else l = mid + 1; } m = min(M, ans + 1); for (int i = 0; i < m; i++) { if(x[i] == y[i]) continue; col[x[i]]++, col[y[i]]++; } queue <int> q; for (int i = 0; i < n; i++) if(!col[i]) q.push(i); for (int i = 0; i < m; i++) { swap(a[x[i]], a[y[i]]); if(x[i] != y[i]) { col[x[i]]--, col[y[i]]--; if(!col[x[i]]) q.push(x[i]); if(!col[y[i]]) q.push(y[i]); ind[a[x[i]]] = x[i]; ind[a[y[i]]] = y[i]; } while(!q.empty() && q.front() == a[q.front()]) q.pop(); if(q.empty()) P[i] = Q[i] = 0; else { int i1 = q.front(); //cout << i1 << endl; P[i] = i1; Q[i] = ind[i1]; swap(a[P[i]], a[Q[i]]); ind[a[P[i]]] = P[i]; ind[a[Q[i]]] = Q[i]; q.pop(); } } return m; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |