Submission #790057

#	Time	Username	Problem	Language	Result	Execution time	Memory
790057		peteza	Sorting (IOI15_sorting)	C++14	100 / 100	141 ms	16624 KiB

sorting

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

int cur[200005], N;
bool vis[200005];
int pos[200005];

int countcompo() {
	for(int j=0;j<=N;j++) vis[j] = 0;
	int cnt = 0;
	for(int i=0;i<N;i++) {
		if(vis[i]) continue;
		vis[i] = 1;
		cnt++;
		int j=i;
		do vis[j=cur[j]] = 1; while(j != i);
	}
	return cnt;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ::N = N;
	for(int i=0;i<N;i++) cur[i] = S[i];
	memset(P, 0, 4*M); memset(Q, 0, 4 * M);
	if(countcompo() == N) return 0;

	int l=0, r=M;
	while(l <= r) {
		int mid = (l+r) >> 1;
		for(int i=0;i<=mid;i++)
			swap(cur[X[i]], cur[Y[i]]);
		if(N-countcompo()<=mid+1) r=mid-1;
		else l=mid+1;
		for(int i=mid;i>=0;i--)
			swap(cur[X[i]], cur[Y[i]]);
	}

	for(int i=l;i<M;i++) {
		for(int j=0;j<=l;j++) swap(cur[X[j]], cur[Y[j]]);
		int cnt = N-countcompo();
		if(cnt <= i+1) { //check if after swapping i, minimum is less than that of i+1
			//if so then return 
			memset(vis, 0, sizeof vis);
			vector<pair<int, int>> ans;
			for(int i=0;i<N;i++) {
				if(!vis[i]) {
					vis[i] = 1;
					int l = i, j = cur[i];
					while(j != i) {
						vis[j] = 1;
						ans.emplace_back(l, j); l = j;
						j = cur[j];
					}
				}
			}

			int k = 0;
			for(int i=0;i<N;i++) pos[S[i]] = i;
			for(int j=0;j<=i;j++) {
				swap(pos[S[X[j]]], pos[S[Y[j]]]);
				swap(S[X[j]], S[Y[j]]);
				if(!ans.empty()) {
					P[k] = pos[ans.back().first];
					Q[k++] = pos[ans.back().second];
					ans.pop_back();
				}
			}
			return i+1;
		}
	}
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:22:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   22 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:5:18: note: shadowed declaration is here
    5 | int cur[200005], N;
      |                  ^
sorting.cpp:46:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   46 |    for(int i=0;i<N;i++) {
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:49:10: warning: declaration of 'l' shadows a previous local [-Wshadow]
   49 |      int l = i, j = cur[i];
      |          ^
sorting.cpp:28:6: note: shadowed declaration is here
   28 |  int l=0, r=M;
      |      ^
sorting.cpp:59:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   59 |    for(int i=0;i<N;i++) pos[S[i]] = i;
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
   72 | }
      | ^

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