Submission #1264322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264322		gustavo_d	Sorting (IOI15_sorting)	C++17	0 / 100	1 ms	584 KiB

sorting

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

const int MAXN = 2e5;

int p[MAXN], pVal[MAXN];

int findSwapPairs(int n, int P[], int m, int hisX[], int hisY[], int myX[], int myY[]) {
    int l = 0, r = m; int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		for (int i=0; i<n; i++) {
			p[i] = P[i];
			pVal[P[i]] = i;
		}
		
		for (int i=0; i<mid; i++) swap(p[hisX[i]], p[hisY[i]]);
		vector<bool> mark(n, false);
		vector<pair<int, int>> ops;
		for (int i=0; i<n; i++) {
			vector<int> cycle;
			int j = i;
			// cerr << "cycle:";
			while (!mark[j]) {
				mark[j] = true;
				cycle.push_back(p[j]);
				// cerr << j << ' ';
				j = p[j];
			}
			for (int k=1; k<(int)cycle.size(); k++)
				ops.emplace_back(cycle[0], cycle[k]);
		}

		bool check = (int)ops.size() <= mid;

		for (int i=0; i<n and check; i++) p[i] = P[i];
		for (int i=0; i<mid and check; i++) {
			// executa i dele
			int val1 = p[hisX[i]], val2 = p[hisY[i]];
			swap(p[hisX[i]], p[hisY[i]]);
			swap(pVal[val1], pVal[val2]);

			// faz sua i
			myX[i] = pVal[ops[i].first];
			myY[i] = pVal[ops[i].second];
		}

		// cerr << mid << ':' << check << endl;
		if (check) {
			r = mid-1;
			ans = mid;
		} else l = mid+1;
	}
	return ans;
}

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