Submission #288363

#	Time	Username	Problem	Language	Result	Execution time	Memory
288363		Saboon	Sorting (IOI15_sorting)	C++17	100 / 100	272 ms	28024 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int n, x[3*maxn], y[3*maxn], a[maxn], b[maxn], pos[maxn], mex[3*maxn], mey[3*maxn];
bool mark[maxn];

bool check(int Q){
	for (int i = 0; i < n; i++){
		b[i] = a[i];
		pos[a[i]] = i;
	}
	for (int i = 0; i < Q; i++)
		swap(a[x[i]], a[y[i]]);
	int cnt = 0;
	memset(mark, 0, sizeof mark);
	for (int i = 0; i < n; i++){
		int now = i;
		mark[now] = 1;
		while (!mark[a[now]]){
			int last = now;
			now = a[now];
			mark[now] = 1;
			swap(b[x[cnt]], b[y[cnt]]);
			swap(pos[b[x[cnt]]], pos[b[y[cnt]]]);
			mex[cnt] = pos[now], mey[cnt] = pos[last];
			swap(pos[now],pos[last]);
			swap(b[pos[now]], b[pos[last]]);
			cnt ++;
		}
	}
	for (int i = cnt; i < Q; i++)
		mex[i] = mey[i] = 0;
	if (cnt <= Q)
		return true;
	return false;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	n = N;
	for (int i = 0; i < M; i++)
		x[i] = X[i], y[i] = Y[i];
	int lo = -1, hi = M;
	while (hi-lo > 1){
		int mid = (lo + hi) >> 1;
		for (int i = 0; i < n; i++)
			a[i] = S[i];
		if (check(mid))
			hi = mid;
		else
			lo = mid;
	}
	for (int i = 0; i < n; i++)
		a[i] = S[i];
	check(hi);
	for (int i = 0; i < hi; i++)
		P[i] = mex[i], Q[i] = mey[i];
	return hi;
}

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