Submission #414867

#	Time	Username	Problem	Language	Result	Execution time	Memory
414867		Bill_00	Sorting (IOI15_sorting)	C++14	100 / 100	164 ms	20396 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int ss[200005],xx[600005],yy[600005],pp[600005],qq[600005],o[200005],pos[200005];
bool check(int n,int array[]){
	for(int i=0;i<n;i++){
		if(i!=array[i]) return 0;
	}
	return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int l=0,r=M;
    while(l<r){
    	for(int i=0;i<N;i++){
    		o[i]=S[i];
    	}
    	int m=(l+r)>>1,cnt=0;
    	for(int i=0;i<m;i++){
    		swap(o[X[i]],o[Y[i]]);
    	}
    	for(int i=0;i<N;i++){
    		pos[o[i]]=i;
    	}
    	for(int i=0;i<N;i++){
    		if(o[i]!=i){
    			pos[o[i]]=pos[i];
    			swap(o[i],o[pos[i]]);
    			pos[i]=i;
    			cnt++;
    		}
    	}
    	if(cnt<=m){
    		r=m;
    	}
    	else l=m+1;
    }
    for(int i=0;i<N;i++){
    	o[i]=S[i];
    }
    for(int i=0;i<l;i++){
    	swap(o[X[i]],o[Y[i]]);
    }
    for(int i=0;i<N;i++){
    	pos[o[i]]=i;
    }
    vector<pair<int,int> >operation;
    for(int i=0;i<N;i++){
    	if(o[i]!=i){
    		operation.pb({o[i],i});
    		pos[o[i]]=pos[i];
    		swap(o[i],o[pos[i]]);
    		pos[i]=i;
    	}
    }
    for(int i=0;i<N;i++){
    	pos[S[i]]=i;
    }
    for(int i=0;i<l;i++){
    	swap(pos[S[X[i]]],pos[S[Y[i]]]);
    	swap(S[X[i]],S[Y[i]]);
    	if(i>=operation.size()){
    		P[i]=pos[0];
    		Q[i]=pos[0];
    	}
    	else{
    		P[i]=pos[operation[i].first];
    		Q[i]=pos[operation[i].second];
    		swap(pos[S[P[i]]],pos[S[Q[i]]]);
    		swap(S[P[i]],S[Q[i]]);
    	}
    }
    return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:62:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |      if(i>=operation.size()){
      |         ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26