Submission #1263904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263904		gustavo_d	Sorting (IOI15_sorting)	C++17	20 / 100	16 ms	328 KiB

sorting

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

const int MAXN = 2e5;

int p[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];
		for (int i=0; i<mid; i++) swap(p[hisX[i]], p[hisY[i]]);
		
		vector<pair<int, int>> ops(mid, make_pair(0, 0));
		for (int op=0; op<mid; op++) {
			for (int i=0; i<n; i++) {
				if (p[i] != i) {
					int pos = 0;
					for (int j=i+1; j<n; j++) {
						if (p[j] == i) {
							pos = j;
							break;
						}
					}
					ops[op] = {i, pos};
					swap(p[i], p[pos]);
					break;
				}
			}
		}

		bool check = true;
		for (int i=0; i<n and check; i++) {
			if (p[i] != i) check = false;
		}

		if (check) {
			r = mid-1;
			for (int op=0; op<mid; op++) {
				myX[op] = ops[op].first;
				myY[op] = ops[op].second;
			}
			ans = mid;
		} else l = mid+1;
	}
	return ans;
}

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