Submission #1065146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065146		pawned	Sorting (IOI15_sorting)	C++17	100 / 100	136 ms	23248 KiB

sorting

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "sorting.h"

int countcyc(vi perm) {
	int N = perm.size();
	vector<bool> vis(N, false);
	int res = 0;
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vis[i] = true;
			int curr = perm[i];
			while (curr != i) {
				vis[curr] = true;
				curr = perm[curr];
			}
			res++;
		}
	}
	return res;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	vi start;
	for (int i = 0; i < N; i++) {
		start.pb(S[i]);
	}
	int low = 0;
	int high = M;
	int ans = -1;	// minimum number of moves so can sort
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi perm = start;
		for (int j = 0; j < mid; j++) {
			swap(perm[X[j]], perm[Y[j]]);
		}
		if ((N - countcyc(perm)) <= mid) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"ans: "<<ans<<endl;
	// take note of what to swap
	vi perm = start;
	for (int j = 0; j < ans; j++) {
		swap(perm[X[j]], perm[Y[j]]);
	}
/*	cout<<"perm: ";
	for (int x : perm)
		cout<<x<<" ";
	cout<<endl;*/
	// find all cycles, then values to swap
	vector<ii> allp;
	vector<bool> vis(N, false);
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vis[i] = true;
			if (i == perm[i])
				continue;
			vi cyc;
			int curr = i;
			cyc.pb(i);
			while (perm[curr] != i) {
				curr = perm[curr];
				cyc.pb(curr);
				vis[curr] = true;
			}
			int sz = cyc.size();
//			cout<<"sz: "<<sz<<endl;
			for (int i = 0; i < sz - 1; i++) {
				allp.pb({cyc[i], cyc[sz - 1]});
			}
		}
	}
/*	cout<<"allp: ";
	for (ii p : allp)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	// convert vals to swap -> indices to swap
	vi pos(N, -1);
	for (int i = 0; i < N; i++) {
		pos[start[i]] = i;
	}
	vi cpr = start;	// current perm
	vector<ii> moves;
	int K = allp.size();
	for (int i = 0; i < K; i++) {
		int p1 = pos[cpr[X[i]]];
		int p2 = pos[cpr[Y[i]]];
		pos[cpr[X[i]]] = p2;
		pos[cpr[Y[i]]] = p1;
		swap(cpr[X[i]], cpr[Y[i]]);
		moves.pb({pos[allp[i].fi], pos[allp[i].se]});
	}
	for (int i = 0; i < ans - K; i++) {
		moves.pb({0, 0});
	}
/*	cout<<"moves: ";
	for (ii p : moves)
		cout<<"("<<p.fi<<", "<<p.se<<"); ";
	cout<<endl;*/
	for (int i = 0; i < ans; i++) {
		P[i] = moves[i].fi;
		Q[i] = moves[i].se;
	}
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'int countcyc(vi)':
sorting.cpp:16:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |  int N = perm.size();
      |          ~~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |    int sz = cyc.size();
      |             ~~~~~~~~^~
sorting.cpp:83:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   83 |    for (int i = 0; i < sz - 1; i++) {
      |             ^
sorting.cpp:68:11: note: shadowed declaration is here
   68 |  for (int i = 0; i < N; i++) {
      |           ^
sorting.cpp:99:19: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   99 |  int K = allp.size();
      |          ~~~~~~~~~^~

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