Submission #285417

#	Time	Username	Problem	Language	Result	Execution time	Memory
285417		amiratou	Sorting (IOI15_sorting)	C++14	100 / 100	265 ms	13176 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;

int tab[200005],pos[200005],L;
ii ans[200005];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l=0,r=N-1;
	while(l<=r){
		for (int i = 0; i < N; ++i){
			tab[i]=S[i];
			pos[S[i]]=i;
		}
		int med=(l+r)>>1,idx=0;
		for (int i = 0; i < med; ++i)
			swap(pos[tab[X[i]]],pos[tab[Y[i]]]),swap(tab[X[i]],tab[Y[i]]);
		for (int i = 0; i < N; ++i)
		{
			if(tab[i]!=i){
				int k=pos[i];
				ans[idx++]={i,tab[i]};
				swap(pos[tab[i]],pos[i]);
				swap(tab[i],tab[k]);

			}
		}
		if(idx>med)l=med+1;
		else{
			L=med;
			for (int i = 0; i < N; ++i){
				tab[i]=S[i];
				pos[S[i]]=i;
			}
			for (int i = 0; i < med; ++i)
			{
				swap(pos[tab[X[i]]],pos[tab[Y[i]]]),swap(tab[X[i]],tab[Y[i]]);
				if(i<idx)P[i]=pos[ans[i].fi],Q[i]=pos[ans[i].se],swap(tab[P[i]],tab[Q[i]]),swap(pos[ans[i].fi],pos[ans[i].se]);
				else P[i]=Q[i]=0;
			}
			r=med-1;
		}
		
	}
	return L;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:13:39: warning: unused parameter 'M' [-Wunused-parameter]
   13 | 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