제출 #298521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298521		TMJN	정렬하기 (IOI15_sorting)	C++17	100 / 100	172 ms	20548 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 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){
		vp.push_back({0,0});
	}
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:60: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]
   60 |  if(vp.size()!=r+1){
      |     ~~~~~~~~~^~~~~

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