# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
294125 | 2020-09-08T15:44:31 Z | arayi | Sorting (IOI15_sorting) | C++17 | 451 ms | 572 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; const int N = 2e5 + 30; int n, m; int a[N], ind[N], x[N], y[N]; int col[N]; bool stg(int m) { 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()) continue; else { int i1 = q.front(); //cout << i1 << endl; swap(a[i1], a[ind[i1]]); ind[a[i1]] = i1; ind[a[ind[i1]]] = ind[i1]; q.pop(); } } for (int i = 0; i < n; i++) if(a[i] != i) return false; return true; } 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[S[i]] = i; for (int i = 0; i < M; i++) x[i] = X[i], y[i] = Y[i]; for (int i = 0; i <= M; i++) { for (int j = 0; j < n; j++) a[j] = S[j], ind[S[j]] = j, col[j] = 0; if(stg(i)) { m = i; break; } } for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i, col[i] = 0; 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(); } } while(!q.empty() && q.front() == a[q.front()]) q.pop(); //if(!q.empty()) assert(0); return m; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Incorrect | 0 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Incorrect | 0 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Incorrect | 61 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Incorrect | 0 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 451 ms | 572 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 451 ms | 572 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |