제출 #438367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438367		ruadhan	정렬하기 (IOI15_sorting)	C++11	62 / 100	303 ms	17864 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

const int MX = 1e5 + 5;
int n, m;
vector<int> s, x, y;
vector<int> a, revA, en, revEn;

bool valid(int t)
{
	a = s;
	for (int i = 0; i < t; i++)
		swap(a[x[i]], a[y[i]]);
	for (int i = 0; i < n; i++)
		revA[a[i]] = i;
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (a[i] != i)
		{
			int j = revA[i];
			swap(revA[a[i]], revA[a[j]]);
			swap(a[i], a[j]);
			cnt++;
		}
	return cnt <= t;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	n = N, m = M;
	s.resize(N), x.resize(N), y.resize(N), a.resize(N), revA.resize(N), en.resize(N), revEn.resize(N);

	for (int i = 0; i < N; i++)
	{
		s.at(i) = S[i];
		x.at(i) = X[i];
		y.at(i) = Y[i];
	}
	int R = 0;
	for (int b = N / 2; b >= 1; b /= 2)
	{
		while (R + b <= M && !valid(R + b))
			R += b;
	}
	if (R == 0)
		R += (valid(R + 1) ? 0 : 1);
	else
		R++;

	a = s;
	for (int i = 0; i < n; i++)
		revA[a[i]] = i;
	en = a;
	for (int i = 0; i < R; i++)
		swap(en[x[i]], en[y[i]]);
	for (int i = 0; i < n; i++)
		revEn[en[i]] = i;

	queue<pair<int, int>> changes;
	vector<int> tmp = en;

	for (int i = 0; i < n; i++)
		if (tmp[i] != i)
		{
			int j = revEn[i];
			swap(revEn[tmp[i]], revEn[tmp[j]]);
			swap(tmp[i], tmp[j]);
			changes.push({i, j});
		}
	for (int i = 0; i < R; i++)
	{
		swap(revA[a[x[i]]], revA[a[y[i]]]);
		swap(a[x[i]], a[y[i]]);
		if (!changes.empty())
		{
			auto change = changes.front();
			changes.pop();
			P[i] = revA[en[change.first]];
			Q[i] = revA[en[change.second]];
			swap(en[change.first], en[change.second]);
			swap(revA[a[P[i]]], revA[a[Q[i]]]);
			swap(a[P[i]], a[Q[i]]);
		}
		else
			P[i] = Q[i] = 1;
	}

	return R;
}

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