제출 #1264201

#제출 시각아이디문제언어결과실행 시간메모리
1264201gustavo_d정렬하기 (IOI15_sorting)C++17
0 / 100
1 ms580 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5; int p[MAXN]; int findSwapPairs(int n, int P[], int m, int hisX[], int hisY[], int myX[], int myY[]) { int l = 0, r = m; int ans = 0; while (l <= r) { int mid = (l + r) / 2; for (int i=0; i<n; i++) p[i] = P[i]; for (int i=0; i<mid; i++) swap(p[hisX[i]], p[hisY[i]]); vector<pair<int, int>> ops(mid, make_pair(0, 0)); vector<bool> mark(n, false); int swaps = 0; bool check = true; for (int i=0; i<n; i++) { if (mark[i]) continue; vector<int> cycle; int j = i; // cerr << "cycle:"; while (!mark[j]) { mark[j] = true; cycle.push_back(j); // cerr << j << ' '; j = p[j]; } // cerr << '\n'; for (j=1; j<(int)cycle.size(); j++) { if (swaps > mid) { check = false; break; } ops[swaps++] = {cycle[0], cycle[j]}; } } // cerr << mid << ':' << check << endl; if (check) { r = mid-1; for (int op=0; op<mid; op++) { myX[op] = ops[op].first; myY[op] = ops[op].second; } ans = mid; } else l = mid+1; } return ans; }
#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...