Submission #496701

#TimeUsernameProblemLanguageResultExecution timeMemory
496701kevinSorting (IOI15_sorting)C++17
0 / 100
1 ms588 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<int> #define all(x) x.begin(), x.end() #define ca(v) for(auto i:v) cout<<i<<" "; #define nl cout<<"\n" const int MAXN = 5e5 + 5; int findSwapPairs(int N, int* s, int M, int* X, int* Y, int* P, int* Q){ int l = 0; int r = M-1; int ans = M; vi S; for(int i=0; i<N; i++) S.push_back(s[i]); while(l <= r){ int m = (l+r)/2; vi ar = S; for(int i=0; i<=m; i++){ swap(ar[X[i]], ar[Y[i]]); } int cnt = 0; vi vis(N, 0); for(int i=0; i<N; i++) { if(vis[i]) continue; cnt++; int q = i; while(1){ vis[q] = 1; if(vis[ar[q]]) break; q = ar[q]; } } cnt = N - cnt; if(cnt-1 <= m){ ans = m; r = m-1; } else l = m+1; } vi vis(N, 0); vi ar = S; for(int i=0; i<=ans; i++) swap(ar[X[i]], ar[Y[i]]); vi xm, ym; int cnt = 0; for(int i=0; i<N; i++) { if(vis[i]) continue; cnt++; int q = i; while(1){ vis[q] = 1; if(vis[ar[q]]) break; xm.push_back(q); ym.push_back(ar[q]); q = ar[q]; } } vector<int> pos(N); for(int i=0; i<N; i++) pos[S[i]] = i; for(int i=0; i<xm.size(); i++){ swap(pos[S[X[i]]], pos[S[Y[i]]]); swap(S[X[i]], S[Y[i]]); P[i] = pos[S[xm[i]]]; Q[i] = pos[S[ym[i]]]; } for(int i=0; i<N - cnt; i++){ P[i+xm.size()] = 0; S[i+xm.size()] = 0; } return ans+1; } // int main() // { // // ios_base::sync_with_stdio(0); cin.tie(0); // if (fopen("input.in", "r")) freopen("input.in", "r", stdin); // int N, M; cin>>N>>M; // int S[N], X[M], Y[M], P[M], Q[M]; // for(int i=0; i<M; i++) P[i] = Q[i] = 0; // for(int i=0; i<N; i++) cin>>S[i]; // for(int i=0; i<M; i++) cin>>X[i]>>Y[i]; // cout<<findSwapPairs(N, S, M, X, Y, P, Q); // nl; // ca(P); nl; // ca(Q); nl; // }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0; i<xm.size(); i++){
      |                  ~^~~~~~~~~~
#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...