Submission #601936

#TimeUsernameProblemLanguageResultExecution timeMemory
601936PiejanVDCSorting (IOI15_sorting)C++17
74 / 100
1041 ms18980 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[]) { auto sorted = [&] (vector<int>&v) -> bool { for(int i = 0 ; i < n ; i++) if(v[i] != i) return 0; return 1; }; int ans; int l = 0, r = m; while(l <= r) { int T = (l+r)/2; //cout << "T : " << T << '\n'; vector<int>c(n); for(int i = 0 ; i < n ; i++) c[i]= i; for(int i = 0 ; i < T ; i++) swap(c[X[i]], c[Y[i]]); vector<int>go(n, -1); for(int i = 0 ; i < n ; i++) { //assert(go[c[i]] == -1); go[c[i]] = i; } vector<int>v(n); auto S = [&] (int W) { for(int i = 0 ; i < n ; i++) if(v[i] == W) return i; //assert(0); }; vector<int>P_(m), Q_(m); for(int i = 0 ; i < n ; i++) v[i] = s[i]; int cnt = 0; for(int i = 0 ; i < T ; i++) { cnt++; swap(v[X[i]], v[Y[i]]); swap(go[X[i]], go[Y[i]]); int j; for(j = 0 ; j < n ; j++) { if(go[j] != v[j]) { int p = S(go[j]); P_[cnt-1] = p; Q_[cnt-1] = j; swap(v[p], v[j]); break; } } /*cout << " " << i << '\n'; cout << " "; for(auto z : v) cout << z << ' '; cout << '\n';*/ if(j == n) P_[cnt-1] = 0, Q_[cnt-1] = 0; // do the swappings // look for first element not correct in go } if(sorted(v)) { r = T-1; for(int i_ = 0 ; i_ < cnt ; i_++) P[i_] = P_[i_], Q[i_] = Q_[i_]; ans = cnt; } else l = T+1; } return ans; }

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:32:9: warning: control reaches end of non-void function [-Wreturn-type]
   32 |         };
      |         ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:67:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |    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...