제출 #572522

#제출 시각아이디문제언어결과실행 시간메모리
572522MohamedFaresNebili정렬하기 (IOI15_sorting)C++14
74 / 100
1094 ms18280 KiB
#include <bits/stdc++.h> #include "sorting.h" using namespace std; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; #define pb push_back #define pp pop_back #define ff first #define ss second #define lb lower_bound #define all(x) (x).begin(), (x).end() bool can(int N, int S[], int M, int X[], int Y[]) { int s[N], x[M], y[M]; int res[N], pos[N], ind[N]; for(int l = 0; l < N; l++) s[l] = S[l]; for(int l = 0; l < M; l++) x[l] = X[l], y[l] = Y[l]; for(int l = 0; l < N; l++) { res[l] = l; pos[s[l]] = l; } for(int l = 0; l < M; l++) { int i = x[l], j = y[l]; swap(res[i], res[j]); } for(int l = 0; l < N; l++) ind[res[l]] = l; map<int, bool> se; for(int l = 0; l < N; l++) { if(s[l] == ind[l]) continue; se[l] = 1; } for(int l = 0; l < M; l++) { int i = x[l], j = y[l]; swap(s[i], s[j]); swap(pos[s[i]], pos[s[j]]); i = ind[i], j = ind[j]; swap(res[i], res[j]); swap(ind[res[i]], ind[res[j]]); if(se.count(x[l])) se.erase(x[l]); if(se.count(y[l])) se.erase(y[l]); if(s[x[l]] != ind[x[l]]) se[x[l]] = 1; if(s[y[l]] != ind[y[l]]) se[y[l]] = 1; int u = 0, v = 0; if(se.size() != 0) { auto it = se.begin(); u = it->first; v = pos[ind[it->first]]; } swap(s[u], s[v]); swap(pos[s[u]], pos[s[v]]); if(se.count(u)) se.erase(u); if(se.count(v)) se.erase(v); if(s[u] != ind[u]) se[u] = 1; if(s[v] != ind[v]) se[v] = 1; } for(int l = 0; l < N - 1; l++) if(s[l] > s[l + 1]) return 0; return 1; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int lo = 0, hi = M; while(lo <= hi) { int md = (lo + hi) / 2; if(can(N, S, md, X, Y)) { M = md; hi = md - 1; } else lo = md + 1; } int res[N], pos[N], ind[N]; for(int l = 0; l < N; l++) { res[l] = l; pos[S[l]] = l; } for(int l = 0; l < M; l++) { int i = X[l], j = Y[l]; swap(res[i], res[j]); } for(int l = 0; l < N; l++) ind[res[l]] = l; map<int, bool> se; for(int l = 0; l < N; l++) { if(S[l] == ind[l]) continue; se[l] = 1; } for(int l = 0; l < M; l++) { int i = X[l], j = Y[l]; swap(S[i], S[j]); swap(pos[S[i]], pos[S[j]]); i = ind[i], j = ind[j]; swap(res[i], res[j]); swap(ind[res[i]], ind[res[j]]); if(se.count(X[l])) se.erase(X[l]); if(se.count(Y[l])) se.erase(Y[l]); if(S[X[l]] != ind[X[l]]) se[X[l]]; if(S[Y[l]] != ind[Y[l]]) se[Y[l]]; int u = 0, v = 0; if(se.size() != 0) { auto it = se.begin(); u = it->first, v = pos[ind[it->first]]; } swap(S[u], S[v]); swap(pos[S[u]], pos[S[v]]); P[l] = u, Q[l] = v; if(se.count(u)) se.erase(u); if(se.count(v)) se.erase(v); if(S[u] != ind[u]) se[u] = 1; if(S[v] != ind[v]) se[v] = 1; } return M; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...