제출 #1029059

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

sorting

#include "sorting.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MXN = 1e6 + 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];
	for (int i = 0; i < N; 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: 26 / 26