Submission #65482

#	Time	Username	Problem	Language	Result	Execution time	Memory
65482		hamzqq9	Sorting (IOI15_sorting)	C++14	100 / 100	282 ms	14584 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define MAX 200005

int go[MAX],plc[MAX],_S[MAX],vis[MAX];

int get_val(int N) {

	int res=0;

	fill(vis,vis+N,0);

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			int cur=i;

			int sz=0;

			while(!vis[cur]) {

				vis[cur]=1;

				sz++;

				cur=go[cur];

			}

			res+=sz-1;

		}

	}
	
	return res;

}

void do_swap(int upto,int X[],int Y[]) {

	for(int i=0;i<upto;i++) swap(_S[X[i]],_S[Y[i]]);

}

void build_graph(int N) {

	for(int i=0;i<N;i++) plc[_S[i]]=i;

	for(int i=0;i<N;i++) go[plc[i]]=i;

}

bool okey(int N,int upto,int S[],int X[],int Y[]) {

	for(int i=0;i<N;i++) _S[i]=S[i];

	do_swap(upto,X,Y);
	
	build_graph(N);

	return get_val(N)<=upto;

}

void get_ans(int N,int upto,int P[],int Q[],int X[],int Y[],int S[]) {

	fill(vis,vis+N,0);

	int tot=0;

	pair<int,int> swp[MAX];

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			int cur=i;

			while(!vis[cur]) {

				vis[cur]=1;

				if(go[cur]!=i) {

					swp[tot++]={_S[cur],_S[go[cur]]};

				}

				cur=go[cur];

			}

		}

	}

	for(int i=0;i<N;i++) plc[S[i]]=i;

	for(int i=0;i<tot;i++) {

		swap(plc[S[X[i]]],plc[S[Y[i]]]);
		swap(S[X[i]],S[Y[i]]);

		P[i]=plc[swp[i].first];
		Q[i]=plc[swp[i].second];

		swap(plc[S[P[i]]],plc[S[Q[i]]]);
		swap(S[P[i]],S[Q[i]]);

	}

	while(tot<upto) {

		P[tot]=Q[tot]=0;

		tot++;

	}

}

void find_solution(int N,int upto,int S[],int X[],int Y[],int P[],int Q[]) {

	for(int i=0;i<N;i++) _S[i]=S[i];

	do_swap(upto,X,Y);

	build_graph(N);

	get_ans(N,upto,P,Q,X,Y,S);

}

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

	while(bas<=son) {

		if(okey(N,orta,S,X,Y)) son=orta-1;
		else bas=orta+1;

	}

	int ans=bas;

	find_solution(N,ans,S,X,Y,P,Q);

	return ans;

}

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