oj.uz

Submission #765056

# Submission time Handle Problem Language Result Execution time Memory
765056 2023-06-24T08:02:21 Z SanguineChameleon Sorting (IOI15_sorting) C++17
0 / 100
 1 ms 468 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 20;

int A[maxN];
int B[maxN];
int pos[maxN];
int *S;
int *X;
int *Y;
int *P;
int *Q;
int N, M;

bool check(int K) {
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		pos[A[i]] = i;
		B[i] = i;
	}
	for (int i = K - 1; i >= 0; i--) {
		swap(B[X[i]], B[Y[i]]);
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (pos[B[i]] != i) {
			int x = i;
			int y = pos[B[i]];
			swap(A[x], A[y]);
			swap(pos[A[x]], pos[A[y]]);
			cnt++;
		}
	}
	return cnt <= K;
}

void build(int K) {
	for (int i = 0; i < N; i++) {
		A[i] = S[i];
		pos[A[i]] = i;
		B[i] = i;
	}
	for (int i = K - 1; i >= 0; i--) {
		swap(B[X[i]], B[Y[i]]);
	}
	vector<pair<int, int>> swaps;
	for (int i = 0; i < N; i++) {
		if (pos[B[i]] != i) {
			int x = i;
			int y = pos[B[i]];
			swaps.emplace_back(A[x], A[y]);
			swap(A[x], A[y]);
			swap(pos[A[x]], pos[A[y]]);
		}
	}
	swaps.resize(K, make_pair(0, 0));
	for (int i = 0; i < N; i++) {
		pos[S[i]] = i;
	}
	for (int i = 0; i < K; i++) {
		int x = X[i];
		int y = Y[i];
		swap(A[x], A[y]);
		swap(pos[A[x]], pos[A[y]]);
		x = pos[swaps[i].first];
		y = pos[swaps[i].second];
		swap(A[x], A[y]);
		swap(pos[A[x]], pos[A[y]]);
		P[i] = x;
		Q[i] = y;
	}
}

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[]) {
	N = _N;
	S = _S;
	M = _M;
	X = _X;
	Y = _Y;
	P = _P;
	Q = _Q;
	int lt = 0;
	int rt = M;
	int K = -1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			K = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	build(K);
	return K;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 300 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 300 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 0 ms 300 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -