Submission #1226343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226343		faruk	Sorting (IOI15_sorting)	C++20	100 / 100	147 ms	14992 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef pair<int, int> pii;

void get_order(int c, vector<int> &arr, vector<bool>&vis, vector<int> &to_add) {
	if (vis[c])
		return;
	vis[c] = true;

}

bool try_m(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int> tmp(S, S + N), where(N), twher(N);
	for (int j = 0; j < M; j++)	
		swap(tmp[X[j]], tmp[Y[j]]);
	for (int i = 0; i < N; i++)
		where[S[i]] = i, twher[tmp[i]] = i;
	vector<pii> to_swap;
	for (int i = 0; i < N; i++) {
		if (i != tmp[i])
		{
			to_swap.emplace_back(tmp[i], tmp[twher[i]]);
			swap(tmp[i], tmp[twher[i]]);
			swap(twher[tmp[i]], twher[tmp[twher[i]]]);
		}
		
	}
	if (to_swap.size() > M)
		return false;
	int i;
	for (i = 0; i < to_swap.size(); i++) {
		// create temp array and do all the swaps
		swap(S[X[i]], S[Y[i]]);
		swap(where[S[X[i]]], where[S[Y[i]]]);
		
		int get_to_right_place = to_swap[i].first;
		int in_my_place = to_swap[i].second;

		int id1 = where[get_to_right_place], id2 = where[in_my_place];
		swap(S[id1], S[id2]);
		swap(where[S[id1]], where[S[id2]]);
		P[i] = id1, Q[i] = id2;
	}
	for (; i < M; i++)
	{
		P[i] = Q[i] = 0;
		swap(S[X[i]], S[Y[i]]);
	}
	for (int i = 1; i < N; i++)
		if (S[i] < S[i - 1])
			return false;
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int> s(S, S + N);
	int l = 0, r = M + 1, ans = M;
	while (l < r) {
		int mid = (l + r) / 2;
		if (try_m(N, S, mid, X, Y, P, Q))
			ans = mid, r = mid;
		else
			l = mid + 1;
		for (int i = 0; i < N; i++)
			S[i] = s[i];
	}
	try_m(N, S, ans, X, Y, P, Q);

	return ans;
}

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