Submission #202805

#	Time	Username	Problem	Language	Result	Execution time	Memory
202805		spdskatr	Sorting (IOI15_sorting)	C++14	74 / 100	205 ms	30104 KiB

sorting

#include "sorting.h"
#include <cstring>
#include <vector>
#include <utility>
#include <cassert>
#include <cstdio>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

int N, M, s[1000005], x[1000005], y[1000005], state[1000005], seen[1000005], pos[1000005];

int check(int steps) {
	for (int i = 0; i < N; i++) state[i] = s[i];
	for (int i = 0; i < steps; i++) {
		if (x[i] != y[i]) {
			swap(state[x[i]], state[y[i]]);
		}
	}
	int cycles = 0;
	for (int i = 0; i < N; i++) {
		if (!seen[i]) {
			seen[i] = 1;
			cycles++;
			int cur = state[i];
			while (cur != i) {
				seen[cur] = 1;
				cur = state[cur];
			}
		}
	}
	int swaps = N - cycles;
	memset(seen, 0, sizeof(seen));
	return swaps <= steps;
}

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
	N = n;
	M = m;
	for (int i = 0; i < N; i++) s[i] = S[i];
	for (int i = 0; i < M; i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	int lo = -1, hi = M;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) hi = mid;
		else lo = mid;
	}
	// Takes hi number of swaps
	for (int i = 0; i < N; i++) state[i] = s[i];
	for (int i = 0; i < hi; i++) {
		if (x[i] != y[i]) {
			swap(state[x[i]], state[y[i]]);
		}
	}
	int R = 0;
	for (int i = 0; i < N; i++) {
		if (!seen[i]) {
			seen[i] = 1;
			if (state[i] != i) {
				vector<pii> swaps;
				int cur = state[i];
				while (cur != i) {
					// Swap cur with state[cur]
					seen[cur] = 1;
					cur = state[cur];
					swaps.push_back({ cur, state[cur] });
				}
				for (int j = 0; j < swaps.size(); j++) {
					P[R] = swaps[j].fi;
					Q[R] = swaps[j].se;
					R++;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) pos[s[i]] = i, state[i] = s[i];
	// Simulate now - We have to keep track of which positions which elements are in
	assert(R <= hi);
	for (int i = 0; i < R; i++) {
		// Forced turn
		swap(pos[state[x[i]]], pos[state[y[i]]]);
		swap(state[x[i]], state[y[i]]);
		//printf("Swapping %d (%d) and %d (%d)\n", P[i], pos[P[i]], Q[i], pos[Q[i]]);
		swap(pos[P[i]], pos[Q[i]]);
		P[i] = pos[P[i]];
		Q[i] = pos[Q[i]];
		swap(state[P[i]], state[Q[i]]);
	}
	for (int i = R; i < hi; i++) P[i] = Q[i] = 0;
	//printf("End result:");
	//for (int i = 0; i < N; i++) printf(" %d", state[i]);
	//printf("\n");
	return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < swaps.size(); j++) {
                     ~~^~~~~~~~~~~~~~

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