Submission #88239

#	Time	Username	Problem	Language	Result	Execution time	Memory
88239		Pajaraja	Sorting (IOI15_sorting)	C++17	74 / 100	1075 ms	10232 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int p[MAXN],n,m,x[3*MAXN],y[3*MAXN],pi[MAXN];
bool vi[MAXN];
vector<int> z[2];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) 
{
	n=N; m=M; for(int i=0;i<n;i++) p[i]=S[i]; for(int i=0;i<m;i++) {x[i]=X[i]; y[i]=Y[i];}
	int r=0,brc=0;
	for(int i=0;i<n;i++) if(!vi[i]) {brc++; while(!vi[i]) {vi[i]=true; i=p[i];}}
	while(brc+r<n)
	{
		fill(vi,vi+n,false);
		swap(p[X[r]],p[Y[r]]);
		brc=0;
		for(int i=0;i<n;i++) if(!vi[i]) {brc++; while(!vi[i]) {vi[i]=true; i=p[i];}}
		r++;
	}
	fill(vi,vi+n,false);
	for(int i=0;i<n;i++) if(!vi[i]) while(!vi[i]) {vi[i]=true; if(!vi[p[i]]) {z[0].push_back(i); z[1].push_back(p[i]);} i=p[i];}
	for(int i=0;i<n;i++) pi[S[i]]=i;
	for(int i=0;i<r;i++)
	{
		swap(S[X[i]],S[Y[i]]);
		pi[S[X[i]]]=X[i];
		pi[S[Y[i]]]=Y[i];
		if(i>=z[0].size()) P[i]=Q[i]=0;
		else 
		{
			if(z[0][i]<z[1][i]) swap(z[0][i],z[1][i]);
			P[i]=pi[z[0][i]]; 
			Q[i]=pi[z[1][i]];
			swap(S[P[i]],S[Q[i]]);
			pi[S[P[i]]]=P[i];
			pi[S[Q[i]]]=Q[i];
		
		}
	}
	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:29:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>=z[0].size()) P[i]=Q[i]=0;
      ~^~~~~~~~~~~~~

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