Submission #788060

#	Time	Username	Problem	Language	Result	Execution time	Memory
788060		GusterGoose27	Sorting (IOI15_sorting)	C++17	100 / 100	174 ms	29748 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5+5;

int perm[MAXN];
int swap_perm[MAXN]; // the thing at position 1 at the end is currently at position ...
int inv_swap[MAXN]; // the thing at position 1 now will be at position ... at the end
int swap_final[MAXN];
int inv_final[MAXN];
vector<pii> pairs;
int n, m;
vector<pii> swaps_mx;
vector<pii> swaps;

void make_swaps() {
	swaps.clear();
	for (int i = 0; i < n; i++) inv_final[swap_final[i]] = i;
	for (int i = 0; i < n; i++) {
		if (inv_final[i] == i) continue;
		int pos = inv_final[i];
		swaps.push_back(pii(i, pos));
		swap(inv_final[swap_final[i]], inv_final[i]);
		swap(swap_final[i], swap_final[pos]);
	}
}

bool works(int cur) {
	iota(swap_perm, swap_perm+n, 0);
	for (int i = 0; i < cur; i++) swap(swap_perm[pairs[i].first], swap_perm[pairs[i].second]);
	for (int i = 0; i < n; i++) inv_swap[swap_perm[i]] = i;
	for (int i = 0; i < n; i++) swap_final[i] = perm[swap_perm[i]];
	make_swaps();
	if (swaps.size() > cur) return 0;
	while (swaps.size() < cur) swaps.push_back(pii(0, 0));
	for (int i = 0; i < swaps.size(); i++) {
		swap(swap_perm[inv_swap[pairs[i].first]], swap_perm[inv_swap[pairs[i].second]]);
		swap(inv_swap[pairs[i].first], inv_swap[pairs[i].second]);
		swaps[i].first = swap_perm[swaps[i].first];
		swaps[i].second = swap_perm[swaps[i].second];
	}
	swaps_mx.clear();
	for (pii p: swaps) swaps_mx.push_back(p);
	return 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	for (int i = 0; i < n; i++) perm[i] = S[i];
	for (int i = 0; i < m; i++) pairs.push_back(pii(X[i], Y[i]));
	int mn = -1, mx = M+1;
	works(3);
	while (mx > mn+1) {
		int cur = (mn+mx)/2;
		if (works(cur)) mx = cur;
		else mn = cur;
	}
	for (int i = 0; i < mx; i++) {
		P[i] = swaps_mx[i].first;
		Q[i] = swaps_mx[i].second;
	}
	return mx;
}

Compilation message (stderr)

sorting.cpp: In function 'bool works(int)':
sorting.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  if (swaps.size() > cur) return 0;
      |      ~~~~~~~~~~~~~^~~~~
sorting.cpp:40:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |  while (swaps.size() < cur) swaps.push_back(pii(0, 0));
      |         ~~~~~~~~~~~~~^~~~~
sorting.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < swaps.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

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