Submission #396746

#	Time	Username	Problem	Language	Result	Execution time	Memory
396746		rainboy	Sorting (IOI15_sorting)	C11	100 / 100	318 ms	10844 KiB

sorting

#include "sorting.h"
#include <string.h>

#define N	200000

int findSwapPairs(int n, int *pp, int m, int *aa, int *bb, int *ii, int *jj) {
	static char visited[N];
	static int vv[N];
	int h, i, j, r, p, q, u, v, lower, upper, cnt;

	for (i = 0; i < n; i++)
		vv[pp[i]] = i;
	lower = -1, upper = m;
	while (upper - lower > 1) {
		r = (lower + upper) / 2;
		for (h = 0; h < r; h++) {
			p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
			pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
		}
		memset(visited, 0, n * sizeof *visited);
		cnt = 0;
		for (i = 0; i < n; i++)
			if (!visited[i]) {
				visited[i] = 1;
				for (j = pp[i]; !visited[j]; j = pp[j])
					visited[j] = 1, cnt++;
			}
		for (h = r - 1; h >= 0; h--) {
			p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
			pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
		}
		if (cnt <= r)
			upper = r;
		else
			lower = r;
	}
	r = upper;
	for (h = 0; h < r; h++) {
		p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
		pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
	}
	memset(visited, 0, n * sizeof *visited);
	cnt = 0;
	for (i = 0; i < n; i++)
		if (!visited[i]) {
			visited[i] = 1;
			for (j = pp[i]; !visited[j]; j = pp[j])
				visited[j] = 1, ii[cnt] = pp[i], jj[cnt] = pp[j], cnt++;
		}
	for (h = r - 1; h >= 0; h--) {
		if (h < cnt)
			ii[h] = vv[ii[h]], jj[h] = vv[jj[h]];
		else
			ii[h] = 0, jj[h] = 0;
		p = pp[aa[h]], q = pp[bb[h]], u = aa[h], v = bb[h];
		pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
	}
	return r;
}

Compilation message (stderr)

sorting.c: In function 'findSwapPairs':
sorting.c:20:24: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   20 |   memset(visited, 0, n * sizeof *visited);
      |                        ^
sorting.c:42:23: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   42 |  memset(visited, 0, n * sizeof *visited);
      |                       ^

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