Submission #1193715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193715		tkm_algorithms	Sorting (IOI15_sorting)	C++20	100 / 100	192 ms	13944 KiB

sorting

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX = 2e5+5;
int *s, *x, *y, *p, *q, n;
int obj[MAX], cur[MAX];
int orev[MAX], crev[MAX];

bool trial(int t) {
	for (int i = 0; i < n; ++i)obj[i] = i;
	
	for (int i = t-1; i >= 0; --i)swap(obj[x[i]], obj[y[i]]);
	
	for (int i = 0; i < n; ++i)
		orev[obj[i]] = i,
		cur[i] = s[i],
		crev[s[i]] = i;
	
	int pt = 0;
	for (int i = 0; i < t; ++i)	{
		swap(obj[x[i]], obj[y[i]]);
		swap(cur[x[i]], cur[y[i]]);
		crev[cur[x[i]]] = x[i];
		orev[obj[x[i]]] = x[i];
		crev[cur[y[i]]] = y[i];
		orev[obj[y[i]]] = y[i];
		while (pt < n && crev[pt] == orev[pt])pt += 1;
		if (pt == n) {
			p[i] = q[i] = 0;
			continue;
		}
		
		int p1 = crev[pt];
		int p2 = orev[pt];
		p[i] = p1, q[i] = p2;
		swap(cur[p1], cur[p2]);
		crev[cur[p1]] = p1;
		crev[cur[p2]] = p2;
	}
	
	while (pt < n && crev[pt] == orev[pt])pt += 1;
	return (pt == n);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N, s = S, x = X, y = Y, p = P, q = Q;
	int l = 0, r = M;
	while (l != r) {
		int m = l+r>>1;
		if (trial(m))r = m;
		else l = m+1;
	}
	
	trial(l);
	return l;
}

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