Submission #1135436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135436		gyg	Sorting (IOI15_sorting)	C++20	0 / 100	1 ms	576 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;
void 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++) {
		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';

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


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

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

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