Submission #590888

#	Time	Username	Problem	Language	Result	Execution time	Memory
590888		yutabi	Sorting (IOI15_sorting)	C++14	100 / 100	371 ms	16492 KiB

sorting

#include "sorting.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef pair <int,int> ii;


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	M=N;

	int l=0;

	int r=M;

	int m=(l+r)/2;

	vector <ii> ans;

	while(l!=r)
	{
		vector <ii> nw;

		for(int i=0;i<m;i++)
		{
			nw.pb(ii(X[i],Y[i]));
		}

		int s[N];
		int loc[N];

		int fnl[N];
		int fnl_loc[N];

		int temp[N];

		for(int i=0;i<N;i++)
		{
			s[i]=S[i];
			loc[s[i]]=i;

			temp[i]=s[i];
		}

		for(int i=0;i<nw.size();i++)
		{
			swap(temp[nw[i].first],temp[nw[i].second]);
		}

		for(int i=0;i<N;i++)
		{
			fnl[i]=temp[i];

			fnl_loc[fnl[i]]=i;
		}

		int ptr=0;

		while(ptr<N && fnl[ptr]==ptr)
		{
			ptr++;
		}

		vector <ii> nw_ans;

		for(int i=0;i<m;i++)
		{
			swap(s[nw[i].first],s[nw[i].second]);

			swap(loc[s[nw[i].first]],loc[s[nw[i].second]]);

			if(ptr<N)
			{
				int num1=ptr;

				int num2=fnl[ptr];

				nw_ans.pb(ii(loc[num1],loc[num2]));

				swap(s[loc[num1]],s[loc[num2]]);

				swap(loc[num1],loc[num2]);


				swap(fnl[fnl_loc[num1]],fnl[fnl_loc[num2]]);

				swap(fnl_loc[num1],fnl_loc[num2]);
			}

			else
			{
				nw_ans.pb(ii(0,0));
			}

			while(ptr<N && fnl[ptr]==ptr)
			{
				ptr++;
			}
		}

		if(ptr==N)
		{
			ans=nw_ans;

			r=m;
		}

		else
		{
			l=m+1;
		}

		m=(l+r)/2;
	}


	for(int i=0;i<m;i++)
	{
		P[i]=ans[i].first;
		Q[i]=ans[i].second;
	}

	return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int i=0;i<nw.size();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