Submission #426588

#TimeUsernameProblemLanguageResultExecution timeMemory
426588PetiSorting (IOI15_sorting)C++14
100 / 100
212 ms20668 KiB
#include <bits/stdc++.h> #include "sorting.h" using namespace std; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<int> inv(N); for(int i = 0; i < N; i++) inv[S[i]] = i; int l = -1, r = M+1; while(l+1 < r){ int m = (l+r)/2; vector<int> sor(N); for(int i = 0; i < N; i++) sor[i] = S[i]; for(int i = 0; i < m; i++) swap(sor[X[i]], sor[Y[i]]); vector<bool> volt(N, false); int kor = 0; for(int i = 0; i < N; i++){ if(volt[i]) continue; kor++; int x = sor[i]; volt[i] = true; while(x != i){ volt[x] = true; x = sor[x]; } } if(N-kor <= m) r = m; else l = m; } vector<int> S2(N); for(int i = 0; i < N; i++) S2[i] = S[i]; for(int i = 0; i < r; i++) swap(S[X[i]], S[Y[i]]); vector<bool> volt(N, false); vector<pair<int, int>> csere; for(int i = 0; i < N; i++){ if(volt[i]) continue; int x = S[i]; vector<int> v; while(x != i){ v.push_back(x); volt[x] = true; x = S[x]; } volt[i] = true; v.push_back(i); for(int j = 0; j < (int)v.size()-1; j++) csere.push_back(make_pair(v[j], v[j+1])); } int x = 0; for(int i = 0; i < r; i++){ swap(inv[S2[X[i]]], inv[S2[Y[i]]]); swap(S2[X[i]], S2[Y[i]]); if(x < csere.size()){ P[i] = inv[csere[x].first]; Q[i] = inv[csere[x].second]; swap(S2[inv[csere[x].first]], S2[inv[csere[x].second]]); swap(inv[csere[x].first], inv[csere[x].second]); x++; } else P[i] = Q[i] = 0; } return r; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if(x < csere.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...