Submission #1031253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031253		Andrey	Sorting (IOI15_sorting)	C++14	100 / 100	170 ms	22768 KiB

sorting

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

vector<int> haha(200001);
vector<int> bruh(200001);
vector<pair<int,int>> wut(0);

int calc(int n) {
	wut.clear();
	for(int i = 0; i < n; i++) {
		bruh[i] = -1;
	}
	int br = 0;
	for(int i = 0; i < n; i++) {
		if(bruh[i] == -1) {
			br++;
			int p = i;
			vector<pair<int,int>> wow(0);
			while(bruh[p] == -1) {
				bruh[p] = 1;
				wow.push_back({haha[p],haha[haha[p]]});
				p = haha[p];
			}
			wow.pop_back();
			for(int j = 0; j < wow.size(); j++) {
				wut.push_back(wow[j]);
			}
		}
	}
	return n-br;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
	int l = 0,r = n;
	while(l < r) {
		int mid = (l+r)/2;
		for(int j = 0; j < n; j++) {
			haha[j] = s[j];
		}
		for(int j = 0; j < mid; j++) {
			swap(haha[x[j]],haha[y[j]]);
		}
		if(calc(n) <= mid) {
			r = mid;
		}
		else {
			l = mid+1;
		}
	}
	for(int j = 0; j < n; j++) {
		haha[j] = s[j];
	}
	for(int j = 0; j < l; j++) {
		swap(haha[x[j]],haha[y[j]]);
	}
	calc(n);
	vector<int> pos(n);
	for(int i = 0; i < n; i++) {
		haha[i] = s[i];
		pos[haha[i]] = i;
	}
	for(int i = 0; i < l; i++) {
		int a = x[i],b = y[i];
		swap(pos[haha[a]],pos[haha[b]]);
		swap(haha[a],haha[b]);
		if(i >= wut.size()) {
			p[i] = 0;
			q[i] = 0;
		}
		else {
			p[i] = pos[wut[i].first];
			q[i] = pos[wut[i].second];
			swap(haha[pos[wut[i].first]],haha[pos[wut[i].second]]);
			swap(pos[wut[i].first],pos[wut[i].second]);
		}
	}
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int calc(int)':
sorting.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for(int j = 0; j < wow.size(); j++) {
      |                   ~~^~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:67:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   if(i >= wut.size()) {
      |      ~~^~~~~~~~~~~~~
sorting.cpp:34:39: warning: unused parameter 'm' [-Wunused-parameter]
   34 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
      |                                   ~~~~^

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