Submission #414670

#	Time	Username	Problem	Language	Result	Execution time	Memory
414670		ja_kingy	Sorting (IOI15_sorting)	C++14	100 / 100	171 ms	24092 KiB

sorting

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

const int mxN = 2e5;
int n, s[mxN], m, x[mxN], y[mxN], p[mxN], q[mxN], ind[mxN], it;
void set_it(int k) {
	while (it < k) {
		swap(s[x[it]], s[y[it]]);
		it++;
	}
	while (it > k) {
		it--;
		swap(s[x[it]], s[y[it]]);
	}
}

bool can_do(int k) {
	set_it(k);
	int cnt = 0;
	vector<int> seen(n);
	for (int i = 0; i < n; ++i) {
		if (!seen[i]) {
			seen[i] = 1;
			for (int c = s[i]; !seen[c]; c = s[c]) {
				seen[c] = 1;
				p[cnt] = c;
				q[cnt] = s[c];
				cnt++;
			}
		}
	}
	return cnt <= k;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N, m = M;
	copy(S, S+N, s);
	copy(X, X+N, x);
	copy(Y, Y+N, y);
	int lo = 0, hi = N, mid;
	while (lo != hi) {
		mid = lo+hi >> 1;
		if (can_do(mid)) hi = mid;
		else lo = mid+1;
	}
	fill(p,p+n,0);
	fill(q,q+n,0);
	can_do(lo);
	set_it(0);
	for (int i = 0; i < n; ++i) ind[s[i]] = i;
	for (int i = 0; i < lo; ++i) {
		swap(s[x[i]], s[y[i]]);
		swap(ind[s[x[i]]], ind[s[y[i]]]);
		P[i] = ind[p[i]];
		Q[i] = ind[q[i]];
		swap(s[P[i]], s[Q[i]]);
		swap(ind[s[P[i]]], ind[s[Q[i]]]);
	}
	return lo;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:43:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   mid = lo+hi >> 1;
      |         ~~^~~

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