oj.uz

Submission #32166

# Submission time Handle Problem Language Result Execution time Memory
32166 2017-10-01T13:06:45 Z imeimi2000 Sorting (IOI15_sorting) C++14
8 / 100
 4 ms 768 KB 
#include "sorting.h"
#include <vector>
#include <algorithm>

using namespace std;
typedef long long llong;

int * arr;
int * x;
int * y;
int n, m;
int tmp[200000];
bool ch[200000];

bool check(int r) {
	int j, cnt = 0;
	for (int i = 0; i < n; ++i) tmp[i] = arr[i], ch[i] = false;
	for (int i = 0; i < r; ++i) swap(tmp[x[i]], tmp[y[i]]);
	for (int i = 0; i < n; ++i) {
		if (ch[i]) continue;
		ch[i] = true;
		j = tmp[i];
		while (j != i) ++cnt, ch[j] = true, j = tmp[j];
	}
	return cnt <= r;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	arr = S;
	x = X;
	y = Y;
	int s = 0, e = m;
	while (s < e) {
		int t = (s + e) / 2;
		if (check(t)) e = t;
		else s = t + 1;
	}
	for (int i = 0; i < n; ++i) tmp[i] = arr[i];
	for (int i = 0; i < s; ++i) {
		swap(tmp[x[i]], tmp[y[i]]);
	}
	for (int i = 0, j = 0; i < m; ++i) {
		while (j < n && tmp[j] == j) ++j;
		if (j == n) {
			for (; i < m; ++i) P[i] = Q[i] = 0;
		}
		P[i] = tmp[j]; Q[i] = tmp[tmp[j]];
		swap(tmp[j], tmp[tmp[j]]);
	}
	for (int i = 0; i < n; ++i) tmp[arr[i]] = i;
	for (int i = 0; i < s; ++i) {
		int p = P[i], q = Q[i];
		swap(tmp[arr[x[i]]], tmp[arr[y[i]]]);
		swap(arr[x[i]], arr[y[i]]);
		P[i] = tmp[p];
		Q[i] = tmp[q];
		swap(arr[tmp[p]], arr[tmp[q]]);
		swap(tmp[p], tmp[q]);
	}
	return s;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 320 KB Output is correct
2 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -