제출 #1135438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135438		gyg	정렬하기 (IOI15_sorting)	C++20	74 / 100	1096 ms	13756 KiB

sorting

// 0 indexed answer

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 2e5 + 5, M = 1e6 + 5;

int n, m;
arr<int, N> sq;
arr<pii, M> ch;

arr<int, N> cr, ps;
void intl() {
	cr = sq;
	for (int i = 1; i <= n; i++) ps[cr[i]] = i;
}
void swp(int i, int j) {
	int x = cr[i], y = cr[j];
	swap(ps[x], ps[y]);
	swap(cr[i], cr[j]);
}

vec<pii> act;
arr<pii, N> ans;
bool bld(int k) {
	intl();
	for (int i = 1; i <= k; i++) swp(ch[i].fir, ch[i].sec);

	// for (int i = 1; i <= n; i++)
	// 	cout << cr[i] << " ";
	// cout << '\n';

	act.clear();
	for (int i = 1; i <= n; i++) {
		if (cr[i] == i) continue;
		act.push_back({cr[i], i});
		swp(ps[cr[i]], ps[i]);
	}
	// for (pii x : act) cout << x.fir << " " << x.sec << '\n';
	if (act.size() > k) return false;

	intl();
	for (int i = 1; i <= k; i++) {
		swp(ch[i].fir, ch[i].sec);
		if (act.size() < i) ans[i] = {1, 1};
		else {
			ans[i] = {ps[act[i - 1].fir], ps[act[i - 1].sec]};
			swp(ans[i].fir, ans[i].sec);
		}
	}

	// for (int i = 1; i <= n; i++)
	// 	cout << cr[i] << " ";
	// cout << '\n';

	for (int i = 1; i <= n; i++) assert(cr[i] == i);
	return true;
}


int findSwapPairs(int _n, int _sq[], int _m, int _ch0[], int _ch1[], int ans0[], int ans1[]) {
    n = _n, m = _m;
	for (int i = 1; i <= n; i++) sq[i] = _sq[i - 1] + 1;
	for (int i = 1; i <= m; i++) ch[i] = {_ch0[i - 1] + 1, _ch1[i - 1] + 1};

	for (int i = 0; i <= n; i++) {
		if (!bld(i)) continue;
		for (int j = 1; j <= i; j++) 
			ans0[j - 1] = ans[j].fir - 1, ans1[j - 1] = ans[j].sec - 1;
		return i;
	}
	assert(false);
	return -1;
}

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