제출 #1029021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029021		aykhn	정렬하기 (IOI15_sorting)	C++17	74 / 100	42 ms	26564 KiB

sorting

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

using namespace std;

const int MXN = 2e5 + 5;


int p[MXN], ind[MXN], cur[MXN], idx[MXN];
int X[MXN], Y[MXN], S[MXN];

int ok(int mid, int N)
{
	vector<int> s;
	s.clear();
	iota(p, p + N, 0);
	for (int i = 0; i < mid; i++) swap(p[X[i]], p[Y[i]]);
	for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
	for (int i = 0; i < N; i++) s.push_back(ind[i]);
	for (int i = 0; i < mid; i++) 
	{
		swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
		swap(ind[X[i]], ind[Y[i]]);
		swap(cur[X[i]], cur[Y[i]]);
		while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
		{
			s.pop_back();
		}
		int f1 = -1, f2 = -1;
		if (!s.empty())
		{
			f1 = idx[s.back()];
			f2 = idx[p[cur[f1]]];
		}
		if (f1 != -1) 
		{
			swap(cur[f1], cur[f2]);
		}
	}
	int ok = 1;
	for (int i = 0; i < N; i++)
	{
		if (ind[i] != p[cur[i]]) ok = 0;
	}
	return ok;
}

int findSwapPairs(int N, int S1[], int M, int x[], int y[], int P[], int Q[]) 
{
	for (int i = 0; i < M; i++) X[i] = x[i], Y[i] = y[i], S[i] = S1[i];
	int l = 0, r = M;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (ok(mid, N)) r = mid;
		else l = mid + 1;
	}
	vector<int> s;
	iota(p, p + N, 0);
	for (int i = 0; i < l; i++) swap(p[X[i]], p[Y[i]]);
	for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
	for (int i = 0; i < N; i++) s.push_back(i);
	for (int i = 0; i < l; i++) 
	{
		swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
		swap(ind[X[i]], ind[Y[i]]);
		swap(cur[X[i]], cur[Y[i]]);
		while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
		{
			s.pop_back();
		}
		int f1 = -1, f2 = -1;
		if (!s.empty())
		{
			f1 = idx[s.back()];
			f2 = idx[p[cur[f1]]];
		} 
		if (f1 != -1) 
		{
			P[i] = f1, Q[i] = f2;
			swap(cur[f1], cur[f2]);
		}
		else P[i] = Q[i] = 0;
	}
	return l;
}

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