Submission #1291198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291198		kustov_vadim_533	Sorting (IOI15_sorting)	C++20	100 / 100	196 ms	12628 KiB

sorting

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <array>
#include <map>
#include <random>
#include <bitset>
#include <stack>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <chrono>
//#include "towns.h"

using namespace std;

typedef long long ll;
typedef long double ld;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

bool calc(int N, int S[], int T, int X[], int Y[], int P[], int Q[]) {
	vector<int> p1(N), p2(N);
	for (int i = 0; i < N; ++i) {
		p1[i] = S[i];
		p2[i] = S[i];
	}

	for (int i = 0; i < T; ++i) {
		swap(p2[X[i]], p2[Y[i]]);
	}

	vector<int> q1(N), q2(N);
	for (int i = 0; i < N; ++i) {
		q1[p1[i]] = i;
		q2[p2[i]] = i;
	}

	int j = 0;

	for (int i = 0; i < T; ++i) {
		swap(q1[p1[X[i]]], q1[p1[Y[i]]]);
		swap(p1[X[i]], p1[Y[i]]);

		P[i] = 0;
		Q[i] = 0;
		for (; j < N; ++j) {
			if (q2[j] != j) {
				P[i] = q1[j];
				Q[i] = q1[p2[j]];
				break;
			}
		}

		swap(p2[q2[p1[P[i]]]], p2[q2[p1[Q[i]]]]);
		swap(q2[p1[P[i]]], q2[p1[Q[i]]]);

		swap(q1[p1[P[i]]], q1[p1[Q[i]]]);
		swap(p1[P[i]], p1[Q[i]]);
	}
	for (; j < N; ++j) {
		if (q2[j] != j) {
			return false;
		}
	}
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int li = -1, ri = M;
	while (ri - li > 1) {
		int t = (li + ri) / 2;

		if (calc(N, S, t, X, Y, P, Q)) {
			ri = t;
		}
		else {
			li = t;
		}
	}
	calc(N, S, ri, X, Y, P, Q);
	return ri;
}

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