Submission #298518

#	Time	Username	Problem	Language	Result	Execution time	Memory
298518		TMJN	Sorting (IOI15_sorting)	C++17	20 / 100	2 ms	512 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int s[200000];
int k[200000];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	bool f=true;
	for(int i=0;i<N;i++){
		if(S[i]!=i)f=false;
	}
	if(f)return 0;
	int d=0;
	for(int i=0;i<N;i++){
		if(S[i]!=i)d++;
	}
	int l,r;
	l=-1;
	r=M;
	while(l+1!=r){
		int m=(l+r)/2;
		for(int i=0;i<N;i++){
			s[i]=S[i];
		}
		for(int i=0;i<=m;i++){
			swap(s[X[i]],s[Y[i]]);
		}
		for(int i=0;i<N;i++){
			k[s[i]]=i;
		}
		int c=0;
		for(int i=0;i<N;i++){
			if(s[i]!=i){
				c++;
				swap(s[i],s[k[i]]);
				swap(k[i],k[s[k[i]]]);
			}
		}
		if(c<=m+1){
			r=m;
		}
		else{
			l=m;
		}
	}
	for(int i=0;i<N;i++){
		s[i]=S[i];
	}
	for(int i=0;i<=r;i++){
		swap(s[X[i]],s[Y[i]]);
	}
	for(int i=0;i<N;i++){
		k[s[i]]=i;
	}
	vector<pair<int,int>>vp;
	for(int i=0;i<N;i++){
		if(s[i]!=i){
			vp.push_back({s[i],s[k[i]]});
			swap(s[i],s[k[i]]);
			swap(k[s[i]],k[s[k[i]]]);
		}
	}
	if(vp.size()!=r+1){
		for(int i=0;i<N;i++){
			s[i]=S[i];
		}
		for(int i=0;i<N;i++){
			k[s[i]]=i;
		}
		for(int i=0;i<r;i++){
			swap(s[X[i]],s[Y[i]]);
			swap(k[s[X[i]]],k[s[Y[i]]]);
			P[i]=k[vp[i].first];
			Q[i]=k[vp[i].second];
			swap(s[P[i]],s[Q[i]]);
			swap(k[s[P[i]]],k[s[Q[i]]]);
		}
		return r;
	}
	for(int i=0;i<N;i++){
		s[i]=S[i];
	}
	for(int i=0;i<N;i++){
		k[s[i]]=i;
	}
	for(int i=0;i<=r;i++){
		swap(s[X[i]],s[Y[i]]);
		swap(k[s[X[i]]],k[s[Y[i]]]);
		P[i]=k[vp[i].first];
		Q[i]=k[vp[i].second];
		swap(s[P[i]],s[Q[i]]);
		swap(k[s[P[i]]],k[s[Q[i]]]);
	}
	return r+1;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:64:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |  if(vp.size()!=r+1){
      |     ~~~~~~~~~^~~~~

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