Submission #88242

#	Time	Username	Problem	Language	Result	Execution time	Memory
88242		Pajaraja	Sorting (IOI15_sorting)	C++17	100 / 100	239 ms	18716 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int s[MAXN],p[MAXN],n,m,x[3*MAXN],y[3*MAXN],pi[MAXN];
bool vi[MAXN];
vector<int> z[2];
void copy() {for(int i=0;i<n;i++) p[i]=s[i];}
bool provera(int a)
{
	copy();
	int brc=0;
	for(int r=0;r<a;r++) swap(p[x[r]],p[y[r]]);
	fill(vi,vi+n,false);
	for(int i=0;i<n;i++) if(!vi[i]) {brc++; while(!vi[i]) {vi[i]=true; i=p[i];}}
	return brc+a>=n;
}
int binarna(int l,int r)
{
	if(l==r) return l;
	int s=(l+r)/2;
	if(provera(s)) return binarna(l,s);
	return binarna(s+1,r);
}
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++) s[i]=S[i]; for(int i=0;i<m;i++) {x[i]=X[i]; y[i]=Y[i];}
	int r=binarna(0,n);
	copy();
	fill(vi,vi+n,false);
	for(int i=0;i<r;i++) swap(p[X[i]],p[Y[i]]);
	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 binarna(int, int)':
sorting.cpp:21:6: warning: declaration of 's' shadows a global declaration [-Wshadow]
  int s=(l+r)/2;
      ^
sorting.cpp:5:5: note: shadowed declaration is here
 int s[MAXN],p[MAXN],n,m,x[3*MAXN],y[3*MAXN],pi[MAXN];
     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:39: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: 26 / 26