Submission #1195195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195195		DeathIsAwe	Sorting (IOI15_sorting)	C++20	100 / 100	596 ms	30620 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;


vector<pair<int,int>> solve(int n, vector<int> oldvec, int x[], int y[], int m) {
	//cout << m << endl << "=======================" << endl;
	vector<int> newvec = oldvec;
	for (int i=0;i<m;i++) swap(newvec[x[i]], newvec[y[i]]);
	vector<int> newvecpos(n);
	//for (int i=0;i<n;i++) {cout << newvec[i] << endl;}
	for (int i=0;i<n;i++) newvecpos[newvec[i]] = i;

	
	vector<pair<int,int>> swapvals, moves;
	unordered_set<int> visited;
	int val;
	for (int i=0;i<n;i++) {
		if (visited.find(i) != visited.end()) continue;
		val = i;
		while (visited.find(val) == visited.end()) {
			swapvals.pb(mp(val, newvec[val]));
			visited.insert(val);
			val = newvec[val];
		}
		swapvals.pop_back();
	}
	
	//for (pair<int,int> i: swapvals) {
	//	cout << i.ff << ' ' << i.ss << endl;
	//}
	//cout << endl;
	
	if (swapvals.size() > m) return moves;


	vector<int> oldvecpos(n);
	for (int i=0;i<n;i++) oldvecpos[oldvec[i]] = i;
	for (int i=0;i<swapvals.size();i++) {
		swap(oldvec[x[i]], oldvec[y[i]]);
		swap(oldvecpos[oldvec[x[i]]], oldvecpos[oldvec[y[i]]]);
		moves.pb(mp(oldvecpos[swapvals[i].ff], oldvecpos[swapvals[i].ss]));
		swap(oldvecpos[swapvals[i].ff], oldvecpos[swapvals[i].ss]);
		swap(oldvec[oldvecpos[swapvals[i].ff]], oldvec[oldvecpos[swapvals[i].ss]]);
	}
	for (int i=0;i<m-swapvals.size();i++) {
		moves.pb(mp(0, 0));
	}
	return moves;
}


int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
	bool asdf = true;
	for (int i=0;i<n;i++) {
		if (s[i] != i) {
			asdf = false;
			break;
		}
	}
	if (asdf) return 0;

	
	vector<int> seq(n);
	for (int i=0;i<n;i++) seq[i] = s[i];
	vector<pair<int,int>> tempans, ans;
	int top = m, bottom = 0, middle;
	while (top > bottom + 1) {
		middle = (top + bottom) / 2;
		tempans = solve(n, seq, x, y, middle);
		if (tempans.size() == 0) {
			bottom = middle;
		} else {
			top = middle;
			ans = tempans;
		}
	}


	for (int i=0;i<ans.size();i++) {
		p[i] = ans[i].ff;
		q[i] = ans[i].ss;
	}
	return ans.size();
}

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