Submission #52113

#	Time	Username	Problem	Language	Result	Execution time	Memory
52113		kingpig9	Sorting (IOI15_sorting)	C++11	100 / 100	492 ms	23212 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
int M;
int S[MAXN];
int X[MAXN], Y[MAXN];
int P[MAXN], Q[MAXN];
bool vis[MAXN];

int cur[MAXN], ind[MAXN];

bool moo (int nsteps, bool dbg = false) {
	for (int i = 0; i < N; i++) {
		cur[i] = S[i];
	}

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

	//check if you can do it
	vector<pii> swaps;
	for (int i = 0; i < N; i++) {
		while (cur[i] != i) {
			swaps.push_back({cur[i], cur[cur[i]]});
			swap(cur[i], cur[cur[i]]);
		}
	}

	if (swaps.size() > nsteps) {
		return false;
	}

	while (swaps.size() < nsteps) {
		swaps.push_back({0, 0});
	}

	for (int i = 0; i < N; i++) {
		cur[i] = S[i];
		ind[cur[i]] = i;
	}

	for (int i = 0; i < nsteps; i++) {
		int x = X[i], y = Y[i];
		swap(ind[cur[x]], ind[cur[y]]);
		swap(cur[x], cur[y]);

		x = swaps[i].fi;
		y = swaps[i].se;
		P[i] = ind[x];
		Q[i] = ind[y];
		swap(cur[ind[x]], cur[ind[y]]);
		swap(ind[x], ind[y]);
	}
	return true;
}

int findSwapPairs (int nn, int ss[], int mm, int xx[], int yy[], int ansp[], int ansq[]) {
	N = nn;
	for (int i = 0; i < N; i++) {
		S[i] = ss[i];
	}
	M = mm;
	for (int i = 0; i < M; i++) {
		X[i] = xx[i];
		Y[i] = yy[i];
		if (X[i] > Y[i]) {
			swap(X[i], Y[i]);
		}
	}

	int lo = -1, hi = M;	//lo is not possible, hi is
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (moo(mid)) {
			hi = mid;
		} else {
			lo = mid;
		}
	}

	moo(hi);
	for (int i = 0; i < hi; i++) {
		ansp[i] = P[i];
		ansq[i] = Q[i];
	}
	return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'bool moo(int, bool)':
sorting.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (swaps.size() > nsteps) {
      ~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (swaps.size() < nsteps) {
         ~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:25:34: warning: unused parameter 'dbg' [-Wunused-parameter]
 bool moo (int nsteps, bool dbg = false) {
                                  ^~~~~

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