제출 #119283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119283		eohomegrownapps	정렬하기 (IOI15_sorting)	C++14	100 / 100	193 ms	21028 KiB

sorting

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

int howManySwaps(int check, int N, vector<int> S, int* X, int* Y, vector<int> el2ind){
	//cout<<"how many "<<check<<endl;
	for (int i = 0; i<check; i++){
		int tmp = S[X[i]];
		S[X[i]]=S[Y[i]];
		S[Y[i]]=tmp;
		tmp = el2ind[S[Y[i]]];
		el2ind[S[Y[i]]]=el2ind[S[X[i]]];
		el2ind[S[X[i]]]=tmp;
		/*for (int t=0; t<N; t++){
		cout<<S[t]<<" ";
	}cout<<endl;*/
	}
	//cout<<"done"<<endl;
	int swaps = 0;
	/*for (int t=0; t<N; t++){
		cout<<S[t]<<" ";
	}cout<<endl;*/
	for (int i = 0; i<N; i++){
		if (S[i]==i){
			continue;
		}
		//swapping S[i] and S[el2ind[i]]
		int a = el2ind[S[el2ind[i]]], b = el2ind[S[i]], c=S[i], d=S[el2ind[i]];
		int tmp = S[i];
		S[i]=i;
		S[el2ind[i]]=tmp;
		el2ind[c]=a;
		el2ind[d]=b;
		swaps++;
		/*for (int t=0; t<N; t++){
		cout<<S[t]<<" ";
	}cout<<endl;*/
	}
	//cout<<swaps<<endl;
	return swaps;
}

vector<pair<int,int> > answer;

void pushToAns(int check, int N, vector<int> S, int* X, int* Y, vector<int> el2ind){
	//cout<<"how many "<<check<<endl;
	for (int i = 0; i<check; i++){
		int tmp = S[X[i]];
		S[X[i]]=S[Y[i]];
		S[Y[i]]=tmp;
		tmp = el2ind[S[Y[i]]];
		el2ind[S[Y[i]]]=el2ind[S[X[i]]];
		el2ind[S[X[i]]]=tmp;
	}
	int swaps = 0;
	/*for (int t=0; t<N; t++){
		cout<<S[t]<<" ";
	}cout<<endl;*/
	for (int i = 0; i<N; i++){
		if (S[i]==i){
			continue;
		}
		answer.push_back(make_pair(i,el2ind[i]));
		//swapping S[i] and S[el2ind[i]]
		int a = el2ind[S[el2ind[i]]], b = el2ind[S[i]], c=S[i], d=S[el2ind[i]];
		int tmp = S[i];
		S[i]=i;
		S[el2ind[i]]=tmp;
		el2ind[c]=a;
		el2ind[d]=b;
		swaps++;
		/*for (int t=0; t<N; t++){
		cout<<S[t]<<" ";
	}cout<<endl;*/
	}
	//cout<<swaps<<endl;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int> seq(S,S+N);
	vector<int> el2ind(N,0);
	for (int i = 0; i<N; i++){
		el2ind[seq[i]]=i;
	}
	//binary search
	int l = 0, r = M;
	//find first element with success
	int count,mid;
	while (l<=r){
		//cout<<l<<" "<<r<<endl;
		mid = (l+r)/2;
		count = howManySwaps(mid,N,seq,X,Y,el2ind);
		//cout<<count<<" "<<mid<<endl;
		if (count<=mid){
			r=mid-1;
		} else {
			l=mid+1;
		}
	}
	pushToAns(l,N,seq,X,Y,el2ind);
	//cout<<"answer"<<endl;
	/*for (auto a : answer){
		cout<<a.first<<" "<<a.second<<endl;
	}*/
	if (count<l){
		for (int i = count; i<l; i++){
			answer.push_back(make_pair(0,0));
		}
	}

	//for (auto a : answer){
	//	cout<<a.first<<" "<<a.second<<endl;
	//}
	//cout<<l<<endl;
	vector<int> swapmap(N);
	for (int i = 0; i<N; i++){
		el2ind[i]=i;
		swapmap[i]=i;
	}
	if (l==0){
		return 0;
	}
	P[l-1]=answer[l-1].first;
	Q[l-1]=answer[l-1].second;
	//cout<<"format"<<endl;
	for (auto a = l-2; a>=0; a--){
		//X[a], Y[a] swapped
		//cout<<X[a+1]<<" "<<Y[a+1]<<endl;
		int ia = el2ind[X[a+1]];
		int ib = el2ind[Y[a+1]];
		//cout<<ia<<" "<<ib<<endl;
		int tmp = swapmap[ia];
		swapmap[ia]=swapmap[ib];
		swapmap[ib]=tmp;
		
		tmp = el2ind[X[a+1]];
		el2ind[X[a+1]]=el2ind[Y[a+1]];
		el2ind[Y[a+1]]=tmp;
		/*for (int t=0; t<N; t++){
			cout<<swapmap[t]<<" ";
		}cout<<endl;
		for (int t=0; t<N; t++){
			cout<<el2ind[t]<<" ";
		}cout<<endl;*/
		P[a]=swapmap[answer[a].first];
		Q[a]=swapmap[answer[a].second];
	}
	return l;
}

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:105:2: warning: 'count' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (count<l){
  ^~

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