oj.uz

Submission #396740

# Submission time Handle Problem Language Result Execution time Memory
396740 2021-04-30T17:02:21 Z rainboy Sorting (IOI15_sorting) C
74 / 100
 1000 ms 14916 KB 
#include "sorting.h"
#include <assert.h>
#include <stdio.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, cnt, sorted;

	for (i = 0; i < n; i++)
		vv[pp[i]] = i;
	sorted = 1;
	for (i = 0; i < n; i++)
		if (pp[i] != i) {
			sorted = 0;
			break;
		}
	if (sorted)
		return 0;
	for (r = 1; r <= m; r++) {
		int p, q, u, v;

		p = pp[aa[r - 1]], q = pp[bb[r - 1]], u = aa[r - 1], v = bb[r - 1];
		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++;
			}
		if (cnt <= r) {
			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;
			}
			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;
				p = pp[ii[h]], q = pp[jj[h]], u = ii[h], v = jj[h];
				pp[v] = p, vv[p] = v, pp[u] = q, vv[q] = u;
			}
			for (i = 0; i < n; i++)
				assert(pp[i] == i);
			return r;
		}
	}
	return -1;
}

Compilation message

sorting.c: In function 'findSwapPairs':
sorting.c:28:24: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
   28 |   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 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 208 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 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 208 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 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 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 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 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 208 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 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 208 KB Output is correct
21 Correct 2 ms 472 KB Output is correct
22 Correct 2 ms 476 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 420 KB Output is correct
2 Correct 15 ms 472 KB Output is correct
3 Correct 14 ms 420 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 296 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Correct 14 ms 424 KB Output is correct
9 Correct 14 ms 332 KB Output is correct
10 Correct 15 ms 428 KB Output is correct
11 Correct 15 ms 432 KB Output is correct
12 Correct 9 ms 332 KB Output is correct
13 Correct 14 ms 464 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 420 KB Output is correct
2 Correct 15 ms 472 KB Output is correct
3 Correct 14 ms 420 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 296 KB Output is correct
7 Correct 7 ms 332 KB Output is correct
8 Correct 14 ms 424 KB Output is correct
9 Correct 14 ms 332 KB Output is correct
10 Correct 15 ms 428 KB Output is correct
11 Correct 15 ms 432 KB Output is correct
12 Correct 9 ms 332 KB Output is correct
13 Correct 14 ms 464 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Execution timed out 1079 ms 14916 KB Time limit exceeded
16 Halted 0 ms 0 KB -