Submission #202813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202813	2020-02-18T01:05:15 Z	spdskatr	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KB

sorting

#include "sorting.h"
#include <cstring>
using namespace std;

int N, M, s[2000005], x[2000005], y[2000005], state[2000005], seen[2000005], pos[2000005];

int check(int steps) {
	for (int i = 0; i < N; i++) state[i] = s[i];
	for (int i = 0; i < steps; i++) {
		if (x[i] != y[i]) {
			swap(state[x[i]], state[y[i]]);
		}
	}
	int cycles = 0;
	for (int i = 0; i < N; i++) {
		if (!seen[i]) {
			seen[i] = 1;
			cycles++;
			int cur = state[i];
			while (cur != i) {
				seen[cur] = 1;
				cur = state[cur];
			}
		}
	}
	int swaps = N - cycles;
	memset(seen, 0, sizeof(seen));
	return swaps <= steps;
}

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++) s[i] = S[i];
	for (int i = 0; i < M; i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	int lo = -1, hi = M;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) hi = mid;
		else lo = mid;
	}
	// Takes hi number of swaps
	for (int i = 0; i < N; i++) state[i] = s[i];
	for (int i = 0; i < hi; i++) {
		if (x[i] != y[i]) {
			swap(state[x[i]], state[y[i]]);
		}
	}
	int R = 0;
	for (int i = 0; i < N; i++) {
		if (!seen[i]) {
			seen[i] = 1;
			if (state[i] != i) {
				int cur = state[i];
				while (cur != i) {
					// Swap cur with state[cur]
					seen[cur] = 1;
					cur = state[cur];
					assert(R < M);
					P[R] = cur;
					Q[R] = state[cur];
					R++;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) pos[s[i]] = i, state[i] = s[i];
	assert(R <= hi && hi <= M);
	for (int i = 0; i < R; i++) {
		swap(pos[state[x[i]]], pos[state[y[i]]]);
		swap(state[x[i]], state[y[i]]);
		swap(pos[P[i]], pos[Q[i]]);
		P[i] = pos[P[i]];
		Q[i] = pos[Q[i]];
		swap(state[P[i]], state[Q[i]]);
	}
	for (int i = R; i < hi; i++) P[i] = Q[i] = 0;
	return hi;
}

Compilation message

sorting.cpp: In function 'int check(int)':
sorting.cpp:11:4: error: 'swap' was not declared in this scope
    swap(state[x[i]], state[y[i]]);
    ^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:4: error: 'swap' was not declared in this scope
    swap(state[x[i]], state[y[i]]);
    ^~~~
sorting.cpp:62:6: error: 'assert' was not declared in this scope
      assert(R < M);
      ^~~~~~
sorting.cpp:62:6: note: suggested alternative: 'short'
      assert(R < M);
      ^~~~~~
      short
sorting.cpp:71:2: error: 'assert' was not declared in this scope
  assert(R <= hi && hi <= M);
  ^~~~~~
sorting.cpp:71:2: note: suggested alternative: 'short'
  assert(R <= hi && hi <= M);
  ^~~~~~
  short
sorting.cpp:73:3: error: 'swap' was not declared in this scope
   swap(pos[state[x[i]]], pos[state[y[i]]]);
   ^~~~