제출 #1248563

#제출 시각아이디문제언어결과실행 시간메모리
1248563KindaGoodGamesSorting (IOI15_sorting)C++20
20 / 100
1 ms584 KiB
#include<bits/stdc++.h> #include "sorting.h" using namespace std; #define pii pair<int,int> vector<pii> swaps; vector<pii> evil; vector<int> arr; int n; vector<pii> insertion_sort(vector<int> arr, vector<int> fin, int m){ vector<int> pos(n); vector<int> posF(n); for(int i = 0; i < n; i++){ pos[arr[i]] = i; posF[fin[i]] = i; } auto doSwap = [&](int a, int b){ swap(arr[a], arr[b]); pos[arr[a]] = a; pos[arr[b]] = b; }; vector<pii> ops; for(int i = 0; i < n; i++){ if (ops.size() > m) break; if(fin[i] == i) continue; doSwap(evil[ops.size()].first,evil[ops.size()].second); // element that is currently at the position of i int oth = fin[posF[i]]; int p = fin[i]; doSwap(pos[oth],pos[p]); ops.push_back({pos[oth],pos[p]}); swap(fin[i], fin[posF[i]]); posF[fin[posF[i]]] = posF[i]; posF[fin[i]] = i; } return ops; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; int ops = 0; arr.resize(N); evil.resize(M); for(int i = 0; i < M; i++){ evil[i] = {X[i], Y[i]}; } for(int i = 0; i < n; i++){ arr[i] = S[i]; } vector<int> cur = arr; int l = 0, r = M; int b = M; while(l <= r){ int mid = (l+r)/2; cur = arr; for(int i = 0; i < mid; i++){ swap(cur[evil[i].first], cur[evil[i].second]); } auto moves = insertion_sort(arr,cur, mid); if(moves.size() <= mid){ b = min(b, mid); r = mid-1; }else{ l = mid+1; } } cur = arr; for(int i = 0; i < b; i++){ swap(cur[evil[i].first], cur[evil[i].second]); } vector<pii> moves = insertion_sort(arr,cur,b); for(int j = 0; j < moves.size(); j++){ P[j] = moves[j].first; Q[j] = moves[j].second; } for(int j = moves.size(); j <= b-1; j++){ P[j] = Q[j] = 0; } return moves.size(); }
#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...