Submission #986371

#	Time	Username	Problem	Language	Result	Execution time	Memory
986371		Pyqe	Sorting (IOI15_sorting)	C++17	100 / 100	140 ms	25392 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

long long a[200069],dsu[200069],pst[200069],pr[200069];

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

int findSwapPairs(int n,int aa[],int m,int ka[],int la[],int sq[],int sq2[])
{
	long long i,j,lh,rh,md,zz,c;
	
	for(lh=0,rh=m;lh<=rh;)
	{
		md=(lh+rh)/2;
		for(i=0;i<n;i++)
		{
			a[i]=aa[i];
			dsu[i]=i;
		}
		for(i=0;i<md;i++)
		{
			swap(a[ka[i]],a[la[i]]);
		}
		c=0;
		for(i=0;i<n;i++)
		{
			c+=fd(i)!=fd(a[i]);
			dsu[fd(i)]=fd(a[i]);
		}
		if(c<=md)
		{
			zz=md;
			rh=md-1;
		}
		else
		{
			lh=md+1;
		}
	}
	for(i=0;i<n;i++)
	{
		a[i]=aa[i];
		pst[i]=i;
		pr[i]=i;
	}
	for(i=0;i<zz;i++)
	{
		swap(a[ka[i]],a[la[i]]);
		sq[i]=0;
		sq2[i]=0;
	}
	for(i=zz-1;i+1;i--)
	{
		swap(pst[pr[ka[i]]],pst[pr[la[i]]]);
		swap(pr[ka[i]],pr[la[i]]);
	}
	for(j=0,i=0;i<zz;i++)
	{
		swap(pst[pr[ka[i]]],pst[pr[la[i]]]);
		swap(pr[ka[i]],pr[la[i]]);
		for(;j<n&&a[j]==j;j++);
		if(j==n)
		{
			break;
		}
		sq[i]=pst[j];
		sq2[i]=pst[a[j]];
		swap(a[j],a[a[j]]);
	}
	return zz;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:75:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |   sq[i]=pst[j];
      |         ~~~~~^
sorting.cpp:76:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |   sq2[i]=pst[a[j]];
      |          ~~~~~~~~^
sorting.cpp:79:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return zz;
      |         ^~
sorting.cpp:55:11: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |  for(i=0;i<zz;i++)
      |          ~^~~

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