Submission #1240222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240222		simplemind_31	정렬하기 (IOI15_sorting)	C++20	100 / 100	267 ms	17808 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n;
vector<int> ss,x,y;
vector<pii> ans;
bool check(int m){
	ans.assign(m,{0,0});
	vector<int> plates_sitting_in_pos(n),inverse_of_s(n),s(n),pos_of_plate(n);
	for(int i=0;i<n;i++){
		s[i]=ss[i];
		inverse_of_s[s[i]]=i;
		plates_sitting_in_pos[i]=i;
	}
	for(int i=0;i<m;i++){
		swap(plates_sitting_in_pos[x[i]],plates_sitting_in_pos[y[i]]);
	}
	for(int i=0;i<n;i++){
		pos_of_plate[plates_sitting_in_pos[i]]=i;
	}
	int p=0;
	for(int i=0;i<m;i++){
		swap(s[x[i]],s[y[i]]);
		swap(pos_of_plate[x[i]],pos_of_plate[y[i]]);
		inverse_of_s[s[x[i]]]=x[i];
		inverse_of_s[s[y[i]]]=y[i];
		plates_sitting_in_pos[pos_of_plate[x[i]]]=x[i];
		plates_sitting_in_pos[pos_of_plate[y[i]]]=y[i];
		while(p<n&&inverse_of_s[p]==plates_sitting_in_pos[p]){
			p++;
		}
		if(p==n){
			break;
		}
		pii temp={inverse_of_s[p],plates_sitting_in_pos[p]};
		swap(s[temp.first],s[temp.second]);
		inverse_of_s[s[temp.first]]=temp.first;
		inverse_of_s[s[temp.second]]=temp.second;
		ans[i]=temp;
	}
	while(p<n&&inverse_of_s[p]==plates_sitting_in_pos[p]){
		p++;
	}
	return p==n;
}
int findSwapPairs(int N,int S[],int m,int X[],int Y[],int p[],int q[]){
	n=N;
	ss.assign(n,0);
	x.assign(m,0);
	y.assign(m,0);
	for(int i=0;i<n;i++){
		ss[i]=S[i];
	}
	for(int i=0;i<m;i++){
		x[i]=X[i];
		y[i]=Y[i];
	}
	int l=0,r=m;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	check(l);
	for(int i=0;i<l;i++){
		p[i]=ans[i].first;
		q[i]=ans[i].second;
	}
	return 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