oj.uz

Submission #414670

# Submission time Handle Problem Language Result Execution time Memory
414670 2021-05-31T03:21:44 Z ja_kingy Sorting (IOI15_sorting) C++14
100 / 100
 171 ms 24092 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5;
int n, s[mxN], m, x[mxN], y[mxN], p[mxN], q[mxN], ind[mxN], it;
void set_it(int k) {
	while (it < k) {
		swap(s[x[it]], s[y[it]]);
		it++;
	}
	while (it > k) {
		it--;
		swap(s[x[it]], s[y[it]]);
	}
}

bool can_do(int k) {
	set_it(k);
	int cnt = 0;
	vector<int> seen(n);
	for (int i = 0; i < n; ++i) {
		if (!seen[i]) {
			seen[i] = 1;
			for (int c = s[i]; !seen[c]; c = s[c]) {
				seen[c] = 1;
				p[cnt] = c;
				q[cnt] = s[c];
				cnt++;
			}
		}
	}
	return cnt <= k;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N, m = M;
	copy(S, S+N, s);
	copy(X, X+N, x);
	copy(Y, Y+N, y);
	int lo = 0, hi = N, mid;
	while (lo != hi) {
		mid = lo+hi >> 1;
		if (can_do(mid)) hi = mid;
		else lo = mid+1;
	}
	fill(p,p+n,0);
	fill(q,q+n,0);
	can_do(lo);
	set_it(0);
	for (int i = 0; i < n; ++i) ind[s[i]] = i;
	for (int i = 0; i < lo; ++i) {
		swap(s[x[i]], s[y[i]]);
		swap(ind[s[x[i]]], ind[s[y[i]]]);
		P[i] = ind[p[i]];
		Q[i] = ind[q[i]];
		swap(s[P[i]], s[Q[i]]);
		swap(ind[s[P[i]]], ind[s[Q[i]]]);
	}
	return lo;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:43:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   mid = lo+hi >> 1;
      |         ~~^~~

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 296 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
7 Correct 1 ms 296 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 296 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
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 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 336 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 304 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 296 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
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 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 336 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 2 ms 464 KB Output is correct
22 Correct 2 ms 564 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 588 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 148 ms 20544 KB Output is correct
16 Correct 144 ms 20992 KB Output is correct
17 Correct 161 ms 22588 KB Output is correct
18 Correct 61 ms 18420 KB Output is correct
19 Correct 134 ms 21472 KB Output is correct
20 Correct 143 ms 22116 KB Output is correct
21 Correct 142 ms 22348 KB Output is correct
22 Correct 127 ms 17488 KB Output is correct
23 Correct 146 ms 23128 KB Output is correct
24 Correct 167 ms 22984 KB Output is correct
25 Correct 159 ms 23016 KB Output is correct
26 Correct 136 ms 21992 KB Output is correct
27 Correct 121 ms 21292 KB Output is correct
28 Correct 153 ms 22564 KB Output is correct
29 Correct 153 ms 22608 KB Output is correct
30 Correct 98 ms 20800 KB Output is correct
31 Correct 151 ms 23300 KB Output is correct
32 Correct 150 ms 22184 KB Output is correct
33 Correct 171 ms 23152 KB Output is correct
34 Correct 167 ms 22972 KB Output is correct
35 Correct 135 ms 21204 KB Output is correct
36 Correct 54 ms 19736 KB Output is correct
37 Correct 171 ms 24092 KB Output is correct
38 Correct 162 ms 22876 KB Output is correct
39 Correct 164 ms 23352 KB Output is correct