# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1088454 | 2024-09-14T12:28:02 Z | Pacybwoah | 정렬하기 (IOI15_sorting) | C++17 | 20 ms | 588 KB |
#include "sorting.h" #include<iostream> #include<vector> #include<algorithm> #include<utility> #include<cassert> using namespace std; namespace{ struct DSU{ vector<int> dsu, sz; DSU(int n){ dsu.resize(n + 1); sz.resize(n + 1); for(int i = 1; i <= n; i++) dsu[i] = i, sz[i] = 1; } int query(int x){ if(x == dsu[x]) return x; dsu[x] = query(dsu[x]); return dsu[x]; } void unite(int a, int b){ a = query(a); b = query(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); dsu[b] = a; sz[a] += sz[b]; } }; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int n = N; vector<int> pos(n); for(int i = 0; i < n; i++) pos[S[i]] = i; vector<int> vec(n); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) vec[j] = S[j], pos[S[j]] = j; vector<int> oripos; for(int j = 0; j < n; j++){ swap(vec[X[j]], vec[Y[j]]); swap(pos[vec[X[j]]], pos[vec[Y[j]]]); if(j < i){ swap(vec[P[j]], vec[Q[j]]); swap(pos[vec[P[j]]], pos[vec[Q[j]]]); } if(j == i){ oripos = pos; } } P[i] = oripos[i]; Q[i] = oripos[vec[i]]; } return n; /*int l = 0, r = M; while(l < r){ int mid = (l + r) >> 1; DSU dsu(n); vector<int> vec(n); for(int i = 0; i < n; i++) vec[i] = S[i]; for(int i = 0; i < mid; i++) swap(vec[X[i]], vec[Y[i]]); for(int i = 0; i < n; i++) dsu.unite(vec[i], i); vector<bool> vis(n); int cc = 0; for(int i = 0; i < n; i++){ if(!vis[dsu.query(i)]){ vis[dsu.query(i)] = 1; cc++; } } if(n - cc <= mid) r = mid; else l = mid + 1; } DSU dsu(n); vector<int> pos(n); for(int i = 0; i < l; i++) swap(S[X[i]], S[Y[i]]); for(int i = 0; i < n; i++) dsu.unite(i, S[i]), pos[S[i]] = i; vector<vector<int>> children(n); for(int i = 0; i < n; i++) children[dsu.query(i)].push_back(i); int cur = 0; for(int i = 0; i < n; i++){ if((int)children[i].size() >= 2){ int sz = children[i].size(); for(int j = 0; j < sz - 1; j++){ int id = children[i][j]; P[cur] = id; Q[cur] = pos[id]; swap(S[P[cur]], S[Q[cur]]); swap(pos[S[P[cur]]], pos[S[Q[cur]]]); cur++; } } } while(cur < l - 1){ P[cur] = 0; Q[cur] = 0; cur++; } return l;*/ } // g++ -std=c++17 -Wall -Wextra -fsanitize=undefined -fsanitize=address -Wshadow -o run sorting.cpp grader.cpp
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 0 ms | 348 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 0 ms | 348 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Incorrect | 0 ms | 348 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 588 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 588 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |