Submission #789922

#	Time	Username	Problem	Language	Result	Execution time	Memory
789922		Amylopectin	Sorting (IOI15_sorting)	C++14	100 / 100	130 ms	22304 KiB

sorting

#include "sorting.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
const int mxn = 1e6 + 10;
// const int mxn = 110;
int ctem[mxn] = {},u[mxn] = {},sta[mxn] = {},bac[mxn] = {},s[mxn] = {};
int findSwapPairs(int n, int ss[], int m, int x[], int y[], int p[], int q[]) 
{
	int i,j,cl=0,cr=n,mid,cn,cm,fn,fm,cou;
	for(i=0; i<n; i++)
	{
		s[i] = ss[i];
	}
	while(cl < cr)
	{
		mid = (cl+cr) / 2;
		for(i=0; i<n; i++)
		{
			ctem[i] = i;
			u[i] = 0;
		}
		for(i=mid-1; i>=0; i--)
		{
			cn = ctem[x[i]];
			ctem[x[i]] = ctem[y[i]];
			ctem[y[i]] = cn;
		}
		for(i=0; i<n; i++)
		{
			sta[ctem[i]] = s[i];
		}
		cou = 0;
		for(i=0; i<n; i++)
		{
			if(u[i] == 0)
			{
				cou ++;
				cn = sta[i];
				u[i] = 1;
				while(cn != i)
				{
					u[cn] = 1;
					cn = sta[cn];
				}
			}
		}
		if(n-cou <= mid)
		{
			cr = mid;
		}
		else 
		{
			cl = mid+1;
		}
	}
	for(i=0; i<n; i++)
		{
			ctem[i] = i;
			u[i] = 0;
		}
		for(i=cl-1; i>=0; i--)
		{
			cn = ctem[x[i]];
			ctem[x[i]] = ctem[y[i]];
			ctem[y[i]] = cn;
		}
		for(i=0; i<n; i++)
		{
			sta[ctem[i]] = s[i];
			bac[s[i]] = i;
		}
	cou = 0;
	fn = s[x[cou]];
	s[x[cou]] = s[y[cou]];
	s[y[cou]] = fn;
				
	bac[s[x[cou]]] = x[cou];
	bac[s[y[cou]]] = y[cou];
	for(i=0; i<n; i++)
	{
		if(u[i] == 0)
		{
			cn = sta[i];
			u[i] = 1;
			fm = i;
			while(cn != i)
			{
				
				u[cn] = 1;
				p[cou] = bac[fm];
				q[cou] = bac[cn];
				cou++;
				fn = bac[fm];
				bac[fm] = bac[cn];
				bac[cn] = fn;

				fn = s[bac[fm]];
				s[bac[fm]] = s[bac[cn]];
				s[bac[cn]] = fn;

				fn = s[x[cou]];
				s[x[cou]] = s[y[cou]];
				s[y[cou]] = fn;
							
				bac[s[x[cou]]] = x[cou];
				bac[s[y[cou]]] = y[cou];

				fm = cn;
				cn = sta[cn];
			}
		}
	}
	if(cou < cl)
	{
		for(i=cou; i<cl; i++)
		{
			p[i] = 0;
			q[i] = 0;
		}
	}
	return cl;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:10:8: warning: unused variable 'j' [-Wunused-variable]
   10 |  int i,j,cl=0,cr=n,mid,cn,cm,fn,fm,cou;
      |        ^
sorting.cpp:10:27: warning: unused variable 'cm' [-Wunused-variable]
   10 |  int i,j,cl=0,cr=n,mid,cn,cm,fn,fm,cou;
      |                           ^~
sorting.cpp:8:40: warning: unused parameter 'm' [-Wunused-parameter]
    8 | int findSwapPairs(int n, int ss[], 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