제출 #1092718

#제출 시각아이디문제언어결과실행 시간메모리
1092718triplem5ds정렬하기 (IOI15_sorting)C++14
100 / 100
151 ms11508 KiB
#include "sorting.h" #include "bits/stdc++.h" using namespace std; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<pair<int, int>> ans; auto check = [&](int prefix) { ans.clear(); vector<int> vec(N), vis(N, 0), pos(N); copy(S, S + N, vec.begin()); for (int i = 0; i < prefix; i++) swap(vec[X[i]], vec[Y[i]]); for (int i = 0; i < N; i++) { int cur = i; vis[cur] = 1; while (!vis[vec[cur]]) { ans.push_back({ cur,vec[cur] }); cur = vec[cur]; vis[cur] = 1; } } return ans.size() <= prefix; }; int lo = 0, hi = M; while (lo < hi) { int md = lo + (hi - lo) / 2; if (check(md)) hi = md; else lo = md + 1; } check(lo); reverse(ans.begin(), ans.end()); while (ans.size() < lo) ans.push_back({ 0, 0 }); vector<int> pos(N), vec(N); for (int i = 0; i < N; i++) { pos[i] = vec[i] = i; } for (int i = lo - 1; i >= 0; --i) { P[i] = pos[ans[i].first]; Q[i] = pos[ans[i].second]; swap(pos[vec[X[i]]], pos[vec[Y[i]]]); swap(vec[X[i]], vec[Y[i]]); } return lo; } /* let's say I have an array of pairs(a, b) let's do all swaps of this array at the end of the swaps what I have is the initial position and the final position so */

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In lambda function:
sorting.cpp:24:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |   return ans.size() <= prefix;
      |          ~~~~~~~~~~~^~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:42:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  while (ans.size() < lo) ans.push_back({ 0, 0 });
      |         ~~~~~~~~~~~^~~~
#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...