Submission #77373

#	Time	Username	Problem	Language	Result	Execution time	Memory
77373		shoemakerjo	Sorting (IOI15_sorting)	C++14	20 / 100	4 ms	384 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 myind[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
	}


	int indo = 0;
	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++) {
		myind[S[i]] = i;

	}
	for (int i = 0; i < lo; i++) {
		if (i >= pts.size()) {
			P[i] = Q[i] = 0;
		}
		else {
			P[i] = myind[pts[i].first];
			Q[i] = myind[pts[i].second];
			swap(myind[pts[i].first], myind[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:87:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i >= pts.size()) {
       ~~^~~~~~~~~~~~~
sorting.cpp:53:6: warning: unused variable 'indo' [-Wunused-variable]
  int indo = 0;
      ^~~~

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