# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
294034 | 2020-09-08T14:35:43 Z | arayi | 정렬하기 (IOI15_sorting) | C++17 | 4 ms | 896 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]; 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]; int l = 0, r = M, ans = M; while(l <= r) { int mid = (l + r) / 2; for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i, col[i] = 0; if(stg(mid)) ans = mid, r = mid - 1; else l = mid + 1; } for (int i = 0; i < n; i++) a[i] = S[i], ind[S[i]] = i, col[i] = 0; m = ans; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Incorrect | 1 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Incorrect | 1 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 2 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Incorrect | 1 ms | 384 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 896 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 896 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |