Submission #160825

#TimeUsernameProblemLanguageResultExecution timeMemory
160825davitmargSorting (IOI15_sorting)C++17
20 / 100
3 ms504 KiB
/*DavitMarg*/ #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <list> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() using namespace std; #ifndef death #include "sorting.h" #endif const int N = 200005; int n,q,x[3*N],y[3*N]; vector<int> s,pos; vector<pair<int,int>> solve(int r) { vector<int> a=s,p(n),ind=pos; vector<pair<int,int>> ans; for(int i=0;i<r;i++) swap(a[x[i]],a[y[i]]); for(int i=0;i<n;i++) p[pos[a[i]]]=i; a=s; for(int i=n-1;i>=0;i--) { //cout<<a[i]<<" ,"; if(p[i]!=a[i]) { ans.PB(MP(i,ind[p[i]])); swap(a[i],a[ind[p[i]]]); swap(ind[a[i]],ind[a[ind[p[i]]]]); } } return ans; } int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]) { n=N; for(int i=0;i<n;i++) s.PB(S[i]); pos=s; for(int i=0;i<n;i++) pos[s[i]]=i; q=M; for(int i=0;i<q;i++) { x[i]=X[i]; y[i]=Y[i]; } int l=0,r=n,m,pos=-1; vector<pair<int,int>> ans; while(l<=r) { m=(l+r)/2; if(solve(m).size()<=m) { pos=m; r=m-1; } else l=m+1; } assert(pos!=-1); ans=solve(pos); while(ans.size()<pos) ans.PB(MP(0,0)); for(int j=0;j<ans.size();j++) { P[j]=ans[j].first; Q[j]=ans[j].second; } return pos; } #ifdef death int main() { int N,S[102],M,X[102],Y[102],P[102],Q[102],R; cin>>N; for(int i=0;i<N;i++) cin>>S[i]; cin>>M; for(int i=0;i<M;i++) cin>>X[i]>>Y[i]; R=findSwapPairs(N,S,M,X,Y,P,Q); cout<<R<<endl; for(int i=0;i<R;i++) cout<<P[i]<<" : "<<Q[i]<<endl; for(int i=0;i<R;i++) { swap(S[P[i]],S[Q[i]]); swap(S[X[i]],S[Y[i]]); } for(int i=0;i<N;i++) cout<<S[i]<<" "; cout<<endl; return 0; } #endif /* 2 1 0 2 1 1 0 0 5 0 3 2 4 1 5 0 0 0 0 0 0 0 0 0 0 */

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:62:70: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[])
                                                                      ^
sorting.cpp:32:11: note: shadowed declaration is here
 const int N = 200005;
           ^
sorting.cpp:76:19: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
     int l=0,r=n,m,pos=-1;
                   ^~~
sorting.cpp:35:15: note: shadowed declaration is here
 vector<int> s,pos;
               ^~~
sorting.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(solve(m).size()<=m)
            ~~~~~~~~~~~~~~~^~~
sorting.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size()<pos)
        ~~~~~~~~~~^~~~
sorting.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<ans.size();j++)
              ~^~~~~~~~~~~
#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...