# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
590902 | 2022-07-06T13:51:48 Z | AlperenT | 정렬하기 (IOI15_sorting) | C++17 | 2 ms | 724 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; int swapcnt(vector<int> v){ int cnt = 0, n = v.size(); vector<bool> vis(n, false); for(int i = 0; i < n; i++){ if(!vis[i]){ int x = i; while(!vis[x]){ cnt++; vis[x] = true; x = v[x]; } cnt--; } } return cnt; } int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]){ vector<int> v, v2; v.assign(n, 0); copy(S, S + n, v.begin()); int l = -1, r = M; while(r - l > 1){ int m = l + (r - l) / 2; v2 = v; for(int i = 0; i < m; i++) swap(v2[X[i]], v2[Y[i]]); if(swapcnt(v2) <= m) r = m; else l = m; } vector<pair<int, int>> swaps; vector<bool> vis(n, false); for(int i = 0; i < n; i++){ if(!vis[i]){ vis[i] = true; int x = i; while(!vis[v2[x]]){ vis[x] = true; swaps.push_back({v2[x], v2[v2[x]]}); x = v2[x]; } } } while(swaps.size() < r) swaps.push_back({0, 0}); vector<int> where(n); for(int i = 0; i < n; i++) where[v[i]] = i; for(int i = 0; i < r; i++){ swap(where[v[X[i]]], where[v[Y[i]]]); swap(v[X[i]], v[Y[i]]); P[i] = where[swaps[i].first]; Q[i] = where[swaps[i].second]; swap(where[v[P[i]]], where[v[Q[i]]]); swap(v[P[i]], v[Q[i]]); } assert(is_sorted(v.begin(), v.end())); return r; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 296 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 296 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 296 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Runtime error | 1 ms | 468 KB | Execution killed with signal 6 |
16 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 436 KB | Output is correct |
3 | Runtime error | 1 ms | 724 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 436 KB | Output is correct |
3 | Runtime error | 1 ms | 724 KB | Execution killed with signal 6 |
4 | Halted | 0 ms | 0 KB | - |