oj.uz

Submission #202812

# Submission time Handle Problem Language Result Execution time Memory
202812 2020-02-18T01:04:26 Z spdskatr Sorting (IOI15_sorting) C++14
74 / 100
 206 ms 24700 KB 
#include "sorting.h"
#include <cstring>
#include <vector>
#include <utility>
#include <cassert>
#include <cstdio>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 11 ms 8184 KB Output is correct
5 Correct 12 ms 8184 KB Output is correct
6 Correct 13 ms 8168 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 9 ms 8184 KB Output is correct
4 Correct 11 ms 8184 KB Output is correct
5 Correct 12 ms 8184 KB Output is correct
6 Correct 13 ms 8168 KB Output is correct
7 Correct 12 ms 8184 KB Output is correct
8 Correct 10 ms 8184 KB Output is correct
9 Correct 12 ms 8184 KB Output is correct
10 Correct 16 ms 8184 KB Output is correct
11 Correct 17 ms 8184 KB Output is correct
12 Correct 16 ms 8184 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8184 KB Output is correct
2 Correct 14 ms 8184 KB Output is correct
3 Correct 16 ms 8184 KB Output is correct
4 Correct 16 ms 8184 KB Output is correct
5 Correct 19 ms 8440 KB Output is correct
6 Correct 14 ms 8184 KB Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8312 KB Output is correct
2 Correct 18 ms 8312 KB Output is correct
3 Correct 19 ms 8312 KB Output is correct
4 Correct 21 ms 8312 KB Output is correct
5 Correct 18 ms 8312 KB Output is correct
6 Correct 20 ms 8312 KB Output is correct
7 Correct 18 ms 8312 KB Output is correct
8 Correct 17 ms 8312 KB Output is correct
9 Correct 18 ms 8312 KB Output is correct
10 Correct 18 ms 8312 KB Output is correct
11 Correct 17 ms 8312 KB Output is correct
12 Correct 18 ms 8312 KB Output is correct
13 Correct 22 ms 8440 KB Output is correct
14 Correct 17 ms 8312 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8312 KB Output is correct
2 Correct 18 ms 8312 KB Output is correct
3 Correct 19 ms 8312 KB Output is correct
4 Correct 21 ms 8312 KB Output is correct
5 Correct 18 ms 8312 KB Output is correct
6 Correct 20 ms 8312 KB Output is correct
7 Correct 18 ms 8312 KB Output is correct
8 Correct 17 ms 8312 KB Output is correct
9 Correct 18 ms 8312 KB Output is correct
10 Correct 18 ms 8312 KB Output is correct
11 Correct 17 ms 8312 KB Output is correct
12 Correct 18 ms 8312 KB Output is correct
13 Correct 22 ms 8440 KB Output is correct
14 Correct 17 ms 8312 KB Output is correct
15 Correct 176 ms 22904 KB Output is correct
16 Correct 188 ms 23336 KB Output is correct
17 Correct 205 ms 24056 KB Output is correct
18 Correct 91 ms 19704 KB Output is correct
19 Correct 163 ms 22264 KB Output is correct
20 Correct 178 ms 22776 KB Output is correct
21 Correct 178 ms 22904 KB Output is correct
22 Correct 187 ms 24312 KB Output is correct
23 Correct 194 ms 24700 KB Output is correct
24 Correct 206 ms 24312 KB Output is correct
25 Correct 201 ms 24184 KB Output is correct
26 Execution timed out 25 ms 3808 KB Time limit exceeded (wall clock)
27 Halted 0 ms 0 KB -