Submission #133669

#	Time	Username	Problem	Language	Result	Execution time	Memory
133669		MAMBA	Sorting (IOI15_sorting)	C++17	100 / 100	598 ms	14328 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)

const int MAXN = 2e5 + 10;

int p[MAXN], q[MAXN], arr[MAXN], rra[MAXN];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

	auto check = [&](int lim) -> bool {
		iota(p , p + N , 0);
		iota(q , q + N , 0);
		memcpy(arr , S , N * 4);
		rep(i , 0 , N)
			rra[arr[i]] = i;
		for(int i = lim - 1; ~i; i--) {
			if (X[i] == Y[i]) continue;
			swap(p[X[i]] , p[Y[i]]);
			swap(q[p[X[i]]] , q[p[Y[i]]]);
		}
		int ptr = 0, cnt = 0;
		for(int i = 0; i < lim; i++) {

			if (X[i] != Y[i]) {
				swap(p[X[i]] , p[Y[i]]);
				swap(q[p[X[i]]] , q[p[Y[i]]]);
				swap(arr[X[i]] , arr[Y[i]]);
				swap(rra[arr[X[i]]] , rra[arr[Y[i]]]);
			}

			while (ptr < N && arr[q[ptr]] == ptr) {
				ptr++;
			}
			if (ptr < N) {
				int pos = rra[ptr];
				// as pos bayad bere be q[ptr]
				int sop = q[ptr];
				P[cnt] = pos;
				Q[cnt++] = sop;
				swap(arr[pos] , arr[sop]);
				swap(rra[arr[pos]] , rra[arr[sop]]);

			}
		}
		while (ptr < N && arr[q[ptr]] == ptr) {
			ptr++;
		}

		while (cnt < N) {
			P[cnt] = Q[cnt] = 0;
			cnt++;
		}

		return ptr == N;

	};


	int l = -1 , r = N;

	while (l != r - 1) {

		int mid = l + r >> 1;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}

	check(r);


	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
sorting.cpp:12:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^

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