oj.uz

Submission #396746

# Submission time Handle Problem Language Result Execution time Memory
396746 2021-04-30T17:09:52 Z rainboy Sorting (IOI15_sorting) C
100 / 100
 318 ms 10844 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 1 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 170 ms 8880 KB Output is correct
16 Correct 223 ms 8964 KB Output is correct
17 Correct 305 ms 9880 KB Output is correct
18 Correct 77 ms 6212 KB Output is correct
19 Correct 200 ms 8436 KB Output is correct
20 Correct 226 ms 8788 KB Output is correct
21 Correct 227 ms 8796 KB Output is correct
22 Correct 167 ms 9672 KB Output is correct
23 Correct 189 ms 9800 KB Output is correct
24 Correct 305 ms 9952 KB Output is correct
25 Correct 303 ms 10308 KB Output is correct
26 Correct 223 ms 8680 KB Output is correct
27 Correct 194 ms 8132 KB Output is correct
28 Correct 302 ms 9532 KB Output is correct
29 Correct 268 ms 9828 KB Output is correct
30 Correct 140 ms 7620 KB Output is correct
31 Correct 289 ms 10024 KB Output is correct
32 Correct 184 ms 9500 KB Output is correct
33 Correct 302 ms 10212 KB Output is correct
34 Correct 235 ms 9940 KB Output is correct
35 Correct 209 ms 8516 KB Output is correct
36 Correct 53 ms 6596 KB Output is correct
37 Correct 318 ms 10844 KB Output is correct
38 Correct 299 ms 10112 KB Output is correct
39 Correct 298 ms 10548 KB Output is correct