Submission #835364

#	Time	Username	Problem	Language	Result	Execution time	Memory
835364		Valaki2	Sorting (IOI15_sorting)	C++14	100 / 100	185 ms	35904 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 2e5;

int n, m;

vector<pii > ans;

void upd(pii cur_swap, vector<int> &pos, vector<int> &which, vector<int> &to, vector<int> &where) {
	// cur_swap: position of two places
	int pos_a = cur_swap.fi, pos_b = cur_swap.se;
	int which_a = which[pos_a], which_b = which[pos_b];
	swap(where[which_a], where[which_b]);
	swap(to[pos_a], to[pos_b]);
	swap(which[pos_a], which[pos_b]);
	swap(pos[which_a], pos[which_b]);
}

bool ok(int k, vector<int> which, vector<pii > swaps, bool create_swap_order) {
	swaps.resize(k);
	if(k == 0) {
		for(int i = 1; i <= n; i++) {
			if(which[i] != i) {
				return false;
			}
		}
		return true;
	}
	vector<int> to(1 + n, 0);
	for(int i = 1; i <= n; i++) {
		to[i] = i;
	}
	for(auto it = swaps.rbegin(); it != swaps.rend(); it++) {
		pii p = *it;
		swap(to[p.fi], to[p.se]);
	}
	vector<int> where(1 + n, 0);
	vector<int> pos(1 + n, 0);
	for(int i = 1; i <= n; i++) {
		where[to[i]] = i;
		pos[which[i]] = i;
	}
	vector<int> perm(1 + n, 0);
	for(int i = 1; i <= n; i++) {
		perm[pos[i]] = where[i];
	}
	vector<pii > ans_elem;
	vector<bool> vis(1 + n, false);
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			int x = i;
			int depth = 0;
			vis[x] = true;
			while(!vis[perm[x]]) {
				if(create_swap_order) {
					ans_elem.pb(mp(which[x], which[perm[x]]));
				}
				x = perm[x];
				vis[x] = true;
				depth++;
			}
			cnt += depth;
		}
	}
	if(!create_swap_order) {
		return (cnt <= k);
	}
	while(ans_elem.size() < k) {
		ans_elem.pb(mp(1, 1));
	}
	ans.resize(k);
	for(int i = 0; i < k; i++) {
		pii cur_swap = swaps[i];
		upd(cur_swap, pos, which, to, where);
		ans[i] = mp(pos[ans_elem[i].fi], pos[ans_elem[i].se]);
		upd(ans[i], pos, which, to, where);
	}
	return true;
}

vector<int> which;
vector<pii > swaps;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	which.assign(1 + n, 0);
	for(int i = 1; i <= n; i++) {
		which[i] = S[i - 1] + 1;
	}
	m = M;
	for(int i = 0; i < m; i++) {
		swaps.pb(mp(X[i] + 1, Y[i] + 1));
	}
	int l = -1, r = m + 1;
	while(l < r - 1) {
		int mid = (l + r) / 2;
		if(ok(mid, which, swaps, false)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	int k = r;
	if(k == 0) {
		// no need to modify P/Q here
		return 0;
	}
	ok(k, which, swaps, true);
	for(int i = 0; i < k; i++) {
		P[i] = ans[i].fi - 1;
		Q[i] = ans[i].se - 1;
	}
	return k;
}

Compilation message (stderr)

sorting.cpp: In function 'bool ok(int, std::vector<int>, std::vector<std::pair<int, int> >, bool)':
sorting.cpp:78:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  while(ans_elem.size() < 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