제출 #438344

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

sorting

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

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	int low = 0, high = M, a[N], g[N];

	function<int(int)> find = [&](int v){
		bitset<1<<18> vis;
		for(int i=0; i<N; ++i){
			g[S[i]] = i;
			a[i] = S[i];
			P[i] = Q[i] = 0;
		}
		for(int i=0; i<v; ++i) swap(g[a[X[i]]], g[a[Y[i]]]), swap(a[X[i]], a[Y[i]]);
		vector<array<int, 2>> t;
		function<void(int)> dfs = [&](int u){
			vis[u] = 1;
			if(!vis[g[u]]) t.push_back({u, g[u]}), dfs(g[u]);
		};
		for(int i=0; i<N; ++i){
			if(!vis[g[S[i]]]) dfs(g[S[i]]);
			g[S[i]] = i, a[i] = S[i];
		}
		for(int i=0; i<min(v, (int)t.size()); ++i){
			swap(g[a[X[i]]], g[a[Y[i]]]);
			swap(a[X[i]], a[Y[i]]);
			P[i] = g[t[i][0]], Q[i] = g[t[i][1]];
		}
		return t.size();
	};

	while(low < high){
		int v = (low + high) / 2;
		if(find(v) <= v) high = v;
		else low = v + 1;
	}
	find(low);
	return low;
}

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