Submission #742301

#	Time	Username	Problem	Language	Result	Execution time	Memory
742301		fractlpaca	Sorting (IOI15_sorting)	C++17	8 / 100	88 ms	38720 KiB

sorting

#include "sorting.h"

#include <vector>
#include <algorithm>
#include <utility>
// #include <iostream>

#define v vector
#define fi first
#define se second

using namespace std;

int n, m;
int *s, *x, *y, *p, *q;

v<v<int>> positions;

bool binary_search (int r) {
	v<int> reverse_positions (n, 0);
	for (int i=0; i<n; i++) {
		reverse_positions[positions[r][i]] = i;
	}
	v<pair<int,int>> pairs;
	v<int> working (n, 0);
	for (int i=0; i<n; i++) {
		working[i] = s[reverse_positions[i]];
	}
	v<int> swaps (n, 0);
	for (int i=0; i<n; i++) {
		swaps[i] = i;
	}
	
	int counter = 0;
	// for (int j=0; j<n; j++) cerr<<positions[r][j]<<" ";
	// cerr<<endl;
	// for (int j=0; j<n; j++) cerr<<working[j]<<" ";
	// cerr<<endl;
	for (int i=0; i<n-1; i++) {
		int mi = i;
		for (int j=i+1; j<n; j++) {
			if (working[j] < working[mi]) {
				mi = j;
			}
		}
		if (mi != i) {
			if (++counter > r) return false;
			// cerr<<"INFO "<<r<<" "<<counter<<" "<<i<<" "<<mi<<" "<<reverse_positions[swaps[i]]<<" "<<reverse_positions[swaps[mi]]<<endl;
			int i_d = swaps[positions[counter][reverse_positions[swaps[i]]]];
			int mi_d = swaps[positions[counter][reverse_positions[swaps[mi]]]];
			swap(swaps[i], swaps[mi]);
			swap(working[i], working[mi]);
			// for (int j=0; j<n; j++) cerr<<working[j]<<" ";
			// cerr<<endl;
			pairs.push_back({i_d, mi_d});
		}
	}
	for(int i=0; i<counter; i++) {
		p[i] = pairs[i].fi;
		q[i] = pairs[i].se;
	}
	for(int i=counter; i<r; i++) {
		p[i] = 0;
		q[i] = 0;
	}
	return true;
}

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;
    positions = v<v<int>> (m+1, v<int> (n, 0));
	for (int i=0; i<n; i++) {
		positions[0][i] = i;
	}
	v<int> reverse_positions = positions[0];
	for(int r=1; r<=m; r++) {
		positions[r] = positions[r-1];
		swap(positions[r][reverse_positions[x[r-1]]], positions[r][reverse_positions[y[r-1]]]);
		swap(reverse_positions[x[r-1]], reverse_positions[y[r-1]]);
	}
	int l = -1, r = m;
	while (l+1 < r) {
		int mid = (l+r)/2;
		//cerr<<l<<" "<<r<<" "<<mid<<endl;
		if (binary_search(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return r;
}

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