Submission #71569

#	Time	Username	Problem	Language	Result	Execution time	Memory
71569		Sa1378	Sorting (IOI15_sorting)	C++17	100 / 100	312 ms	14440 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)201*1000)

int b[N],pos[N];
bool mark[N];

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[])
{
	bool flg=1;
	for(int i=0;i<n;i++)if(a[i]!=i)flg=0;
	if(flg)return 0;
    int l=0,r=m+1;
	vector <pair<int,int> > res;
	while(l<r-1)
	{
		int mid=(l+r)/2;
		for(int i=0;i<n;i++)b[i]=a[i],mark[i]=0;
		for(int i=0;i<mid;i++)swap(b[x[i]],b[y[i]]);
		vector <pair<int,int> > vec;
		for(int i=0;i<n;i++)
			if(!mark[i])
			{
				mark[i]=1;
				if(b[i]==i)continue;
				int j=b[i];vec.push_back({i,j});
				while(!mark[j])
				{
					mark[j]=1;
					if(!mark[b[j]])vec.push_back({j,b[j]});
					j=b[j];
				}
			}
		if(vec.size()>mid)l=mid;
		else r=mid,res.swap(vec);
	}
	for(int i=0;i<n;i++)pos[a[i]]=i;
	for(int i=0;i<r;i++)
	{
		if(res.size()<=i){p[i]=q[i]=0;continue;}
		swap(pos[a[x[i]]],pos[a[y[i]]]);
		swap(a[x[i]],a[y[i]]);
		p[i]=pos[res[i].first];q[i]=pos[res[i].second];
		swap(pos[res[i].first],pos[res[i].second]);
		swap(a[pos[res[i].first]],a[pos[res[i].second]]);
	}
	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size()>mid)l=mid;
      ~~~~~~~~~~^~~~
sorting.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(res.size()<=i){p[i]=q[i]=0;continue;}
      ~~~~~~~~~~^~~

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