Submission #797890

#	Time	Username	Problem	Language	Result	Execution time	Memory
797890		QwertyPi	Sorting (IOI15_sorting)	C++14	100 / 100	226 ms	23348 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

bool can(int K, int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	assert(K <= M);
	int s[N], si[N]; for(int i = 0; i < N; i++) s[i] = S[i];
	for(int i = 0; i < K; i++) swap(s[X[i]], s[Y[i]]);
	vector<pair<int, int>> V;
	bool u[N] = {};
	for(int i = 0; i < N; i++){
		if(!u[i] && s[i] != i){
			vector<int> v {i}; int x = s[i];
			while(x != i) v.push_back(x), x = s[x];
			for(auto i : v) u[i] = true;
			for(int j = 1; j < (int) v.size(); j++) V.push_back({v[j - 1], v[j]});
		}
	}
	if((int) V.size() > K) return false;
	for(int i = 0; i < N; i++) s[i] = S[i], si[s[i]] = i;
	for(int i = 0; i < K; i++){
		swap(s[X[i]], s[Y[i]]); swap(si[s[X[i]]], si[s[Y[i]]]);
		if(i < (int) V.size()){
			int a = V[i].first, b = V[i].second;
			P[i] = si[a], Q[i] = si[b]; swap(s[si[a]], s[si[b]]); swap(si[s[si[a]]], si[s[si[b]]]);
		}else{
			P[i] = Q[i] = 0;
		}
	}
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int L = 0, R = M;
	while(L != R){
		int mid = (L + R) / 2;
		if(can(mid, N, S, M, X, Y, P, Q)){
			R = mid;
		}else{
			L = mid + 1;
		}
	}
	can(L, N, S, M, X, Y, P, Q);
	return L;
}

Compilation message (stderr)

sorting.cpp: In function 'bool can(int, int, int*, int, int*, int*, int*, int*)':
sorting.cpp:16:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   16 |    for(auto i : v) u[i] = true;
      |             ^
sorting.cpp:12:10: note: shadowed declaration is here
   12 |  for(int i = 0; i < N; i++){
      |          ^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26