Submission #1291196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291196		kustov_vadim_533	Sorting (IOI15_sorting)	C++20	16 / 100	4 ms	580 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());


int findSwapPairs(int N, int S[], int M, 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 < M; ++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;
	}

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

		P[i] = 0;
		Q[i] = 0;
		for (int j = 0; 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]]);
	}

	return M;
}

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