제출 #572019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572019		CSQ31	정렬하기 (IOI15_sorting)	C++17	100 / 100	169 ms	20524 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
//let K_i = n-number of cycles at step i
//f(i) = max(i,K_i) is non decreasing
const int MAXN = 2e5+1;
bool vis[MAXN];
int p[MAXN],q[MAXN];
void change(int i,int j){
	int a = p[i];
	int b = p[j];
	q[a] = j;
	q[b] = i;
	swap(p[i],p[j]);
}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int>s(n);
	int idx = 0;
	bool ok = 1;
	for(int i=0;i<n;i++)if(S[i] != i)ok = 0;
	if(ok)return 0;
	for(int i=0;i<n;i++)s[i] = S[i];
	int l = 0,r = M-1;
	while(r>=l){
		int mid = (l+r)/2;
		for(int i=0;i<n;i++)S[i] = s[i];
		for(int i=0;i<=mid;i++)swap(S[X[i]],S[Y[i]]);
		int cost = n;
		for(int j=0;j<n;j++)vis[j] = 0;
		for(int j=0;j<n;j++){
			int cur = j;
			if(vis[j])continue;
			while(!vis[cur]){
				vis[cur] = 1;
				cur = S[cur];
			}
			cost--;
		}
		if(cost > mid+1)l = mid+1;
		else r = mid-1;
	}
	idx = l;
	for(int i=0;i<n;i++)S[i] = s[i];
	for(int i=0;i<=idx;i++)swap(S[X[i]],S[Y[i]]);
	vector<array<int,2>>need;
	for(int j=0;j<n;j++)vis[j] = 0;
	for(int j=0;j<n;j++){
		int cur = j;
		if(vis[j])continue;
		while(!vis[cur]){
			vis[cur] = 1;
			cur = S[cur];
			need.push_back({cur,S[cur]});
		}
		need.pop_back();
	}
	//for(auto x:need)cout<<x[0]<<" "<<x[1]<<'\n';
	for(int i=0;i<n;i++){
		p[i] = s[i];
		q[s[i]] = i;
	}
	reverse(need.begin(),need.end());
	for(int i=0;i<=idx;i++){
		change(X[i],Y[i]);
		if(need.empty()){
			P[i] = Q[i] = 0;
			continue;
		}
		//for(int i=0;i<n;i++)cout<<p[i]<<" ";
		//cout<<'\n';
		int v = need.back()[0];
		int u = need.back()[1];
		P[i] = q[v];
		Q[i] = q[u];
		change(q[v],q[u]);
		need.pop_back();
		//for(int i=0;i<n;i++)cout<<p[i]<<" ";
		//cout<<'\n';
	}
	//for(int i=0;i<n;i++)cout<<p[i]<<" ";
   // cout<<'\n';
	return idx+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