Submission #55440

#	Time	Username	Problem	Language	Result	Execution time	Memory
55440		aome	Sorting (IOI15_sorting)	C++17	100 / 100	338 ms	21064 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n;
int S[N], X[N * 3], Y[N * 3];
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 (stderr)

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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26