oj.uz

Submission #55439

# Submission time Handle Problem Language Result Execution time Memory
55439 2018-07-07T11:26:31 Z aome Sorting (IOI15_sorting) C++17
74 / 100
 57 ms 14840 KB 
#include "sorting.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n;
int S[N], X[N], Y[N];
int A[N], B[N], C[N], D[N];
vector< pair<int, int> > vec;

bool check(int len) {
	vec.clear();
	for (int i = 0; i < n; ++i) A[i] = S[i];
	for (int i = 0; i < n; ++i) B[i] = i;
	for (int i = 0; i < n; ++i) C[B[i]] = i;
	for (int i = 0; i < len; ++i) {
		int x = C[X[i]], y = C[Y[i]];
		swap(C[X[i]], C[Y[i]]);
		swap(B[x], B[y]);
	}
	for (int i = 0; i < n; ++i) D[A[i]] = i;
	for (int i = 0; i < n; ++i) {
		if (D[i] == C[i]) continue;
		int x = D[i], y = C[i];
		vec.push_back({x, y});
		swap(D[i], D[A[y]]);
		swap(A[x], A[y]);
	}
	while (vec.size() < len) vec.push_back({0, 0}); 
	return vec.size() == len;
}

int findSwapPairs(int _n, int _S[], int m, int _X[], int _Y[], int P[], int Q[]) {
	n = _n;
	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 l = 0, r = m - 1;
    while (l < r) {
    	int mid = (l + r) >> 1;
    	if (check(mid)) r = mid; else l = mid + 1;
    }
    int len = l;
    check(len);
	for (int i = 0; i < n; ++i) B[i] = i;
	for (int i = 0; i < n; ++i) C[B[i]] = i; 
	for (int i = 0; i < len; ++i) {
		int x = C[X[i]], y = C[Y[i]];
		swap(C[Y[i]], C[X[i]]);
		swap(B[x], B[y]);
		x = vec[i].first, y = vec[i].second;
		P[i] = B[x], Q[i] = B[y];
	} 
	return len;
}

Compilation message

sorting.cpp: In function 'bool check(int)':
sorting.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (vec.size() < len) vec.push_back({0, 0}); 
         ~~~~~~~~~~~^~~~~
sorting.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return vec.size() == len;
         ~~~~~~~~~~~^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 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 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 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 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 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 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 4 ms 768 KB Output is correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 4 ms 768 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Runtime error 57 ms 14840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -