Submission #77375

#	Time	Username	Problem	Language	Result	Execution time	Memory
77375		shoemakerjo	Sorting (IOI15_sorting)	C++14	100 / 100	460 ms	12032 KiB

sorting

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

using namespace std;
#define maxn 200010
#define pii pair<int, int>

int curp[maxn];
bool vis[maxn];
int myplate[maxn];
int plateind[maxn];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;
	int lo = 0;
	int hi = M;

	while (lo < hi) {
		int mid = (lo+hi)/2;
		for (int i = 0; i < N; i++) {
			curp[i] = i;
			vis[i] = false;
		}
		for (int i = 0; i < mid; i++) {
			swap(curp[X[i]], curp[Y[i]]);
		}
		int numcomp = 0;

		//i think the below is good (might be an issue though)
		for (int i = 0; i < N; i++) {
			if (vis[S[i]]) continue;
		
			int cur = S[i];
			vis[cur] = true;
			cur = S[curp[cur]]; //what is where I want to me

			while (cur != S[i]) {
				vis[cur] = true;
				cur = S[curp[cur]];
			}
			
			numcomp++;
		}
		int moves = N - numcomp;
		if (moves <= mid) {
			//we are good to go
			hi = mid;
		}
		else lo = mid+1; //going to have to go further
	}

	for (int i = 0; i < N; i++) {
		curp[i] = i;
		vis[i] = false;
	}
	for (int i = 0; i < lo; i++) {
		swap(curp[X[i]], curp[Y[i]]);
	}
	vector<pii> pts; //swap what plates that thing x and thing y are on
	for (int i = 0; i < N; i++) {
		if (vis[S[i]]) continue;
		int cur = S[i];
		vis[cur] = true;
		if (cur == S[curp[cur]]) continue;
		pts.push_back(pii(cur, S[curp[cur]]));
		cur = S[curp[cur]];
		while (cur != S[i]) {
			vis[cur] = true;
			int nextval = S[curp[cur]];
			if (nextval != S[i]) {
				pts.push_back(pii(cur, nextval));
			}
			cur = nextval;
		}
	}
	
	// cout << "here " << endl;

	for (int i = 0; i < N; i++) {
		myplate[S[i]] = i;
		plateind[i] = i;
		curp[i] = i;

	}
	for (int i = 0; i < lo; i++) {

		int p1 = curp[X[i]];
		int p2 = curp[Y[i]];
		swap(plateind[p1], plateind[p2]);
		swap(curp[X[i]], curp[Y[i]]);

		if (i >= pts.size()) {
			P[i] = Q[i] = 0;
		}
		else {
			P[i] = plateind[myplate[pts[i].first]];
			Q[i] = plateind[myplate[pts[i].second]];
			swap(myplate[pts[i].first], myplate[pts[i].second]);
		}
	}

	// cout << "RETURNING " << lo << endl;

	return lo;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:93:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i >= pts.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