Submission #288397

#	Time	Username	Problem	Language	Result	Execution time	Memory
288397		amoo_safar	Sorting (IOI15_sorting)	C++17	100 / 100	815 ms	19192 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()

using namespace std;

int findSwapPairs(int n, int seq[], int m, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;

	vector<int> per(n), idx(n), mk(n);
	
	int L = -1, R = m, mid;
	int d;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		iota(all(per), 0);
		fill(all(mk), 0);
		d = 0;
		
		for(int i = mid - 1; i >= 0; i--){
			d ++;
			if(X[i] != Y[i])
				swap(per[X[i]], per[Y[i]]);
		}

		for(int i = 0; i < n; i++) idx[per[i]] = i;

		int cnt = 0, nw;
		for(int i = 0; i < n; i++){
			if(mk[seq[i]]) continue;
			cnt ++;
			nw = seq[i];
			do {
				mk[nw] = 1;
				nw = seq[idx[nw]];
			} while(!mk[nw]);
		}

		if(n - cnt <= d) R = mid;
		else L = mid;
	}
	cerr << "! " << R << '\n';


	iota(all(per), 0);
	fill(all(mk), 0);	
	for(int i = R - 1; i >= 0; i--){
		if(X[i] != Y[i])
			swap(per[X[i]], per[Y[i]]);
	}
	
	for(int i = 0; i < n; i++) idx[per[i]] = i;

	set<int> nq;
	for(int i = 0; i < n; i++) if(seq[i] != per[i]) nq.insert(i);

	for(int i = 0; i < R; i++){
		if(X[i] != Y[i]){
			nq.erase(X[i]);
			nq.erase(Y[i]);
			
			swap(seq[X[i]], seq[Y[i]]);
			swap(per[X[i]], per[Y[i]]);

			idx[per[X[i]]] = X[i];
			idx[per[Y[i]]] = Y[i];
		
			if(seq[X[i]] != per[X[i]])
				nq.insert(X[i]);
			if(seq[Y[i]] != per[Y[i]])
				nq.insert(Y[i]);
		}

		if(!nq.empty()){
			int fr = *nq.begin();
			P[i] = fr;
			Q[i] = idx[seq[fr]];
			assert(P[i] != Q[i]);

			nq.erase(P[i]);
			nq.erase(Q[i]);
			
			swap(seq[P[i]], seq[Q[i]]);
		
			if(seq[P[i]] != per[P[i]])
				nq.insert(P[i]);
			if(seq[Q[i]] != per[Q[i]])
				nq.insert(Q[i]);
		}

	}

	for(int i = 0; i < n; i++) assert(seq[i] == i);
	return R;
}

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