Submission #1135439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135439		gyg	Sorting (IOI15_sorting)	C++20	100 / 100	113 ms	20176 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(), act.clear();
	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';

	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(), ans.fill({0, 0});
	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 srch() {
	int lw = 0, hg = n;
	while (lw != hg) {
		int md = (lw + hg) / 2;
		if (bld(md)) hg = md;
		else lw = md + 1;
	}
	return lw;
}

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};

	int k = srch();
	bld(k);
	for (int i = 1; i <= k; i++) 
		ans0[i - 1] = ans[i].fir - 1, ans1[i - 1] = ans[i].sec - 1;
	return k;
}

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