Submission #803032

#	Time	Username	Problem	Language	Result	Execution time	Memory
803032		BT21tata	Sorting (IOI15_sorting)	C++17	100 / 100	239 ms	22620 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;

bool used[200005];
int pos[200005], cur[200005];

bool check(int n, int S[], int m, int X[], int Y[], int P[], int Q[])
{
	for(int i=0; i<n; i++)
		cur[i]=S[i];
	for(int i=0; i<m; i++)
		swap(cur[X[i]], cur[Y[i]]);
	memset(used, 0, sizeof(used));
	vector<pair<int,int>>ans;
	//cout<<"check "<<m<<endl;
	for(int i=0; i<n; i++)
	{
		if(cur[i]!=i and !used[i])
		{
			vector<int>v; v.pb(i);
			int j=cur[i]; used[i]=1;
			while(j!=i)
			{
				v.pb(j);
				used[j]=1;
				j=cur[j];
			}
			//for(int u : v)cout<<u<<' ';cout<<endl;
			for(int j=0; j+1<v.size(); j++)
				ans.pb({v[j], v[j+1]});
		}
	}
	if(ans.size()>m) return 0;
	for(int i=0; i<n; i++)
		pos[S[i]]=i, cur[i]=S[i];
	for(int i=0; i<m; i++)
	{
		swap(cur[X[i]], cur[Y[i]]);
		swap(pos[cur[X[i]]], pos[cur[Y[i]]]);
		if(i<ans.size())
		{
			P[i]=pos[ans[i].F];
			Q[i]=pos[ans[i].S];
			swap(cur[P[i]], cur[Q[i]]);
			swap(pos[cur[P[i]]], pos[cur[Q[i]]]);
		}
		else P[i]=Q[i]=0;
	}
	return 1;
}

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	int l=0, r=n-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(n, S, mid, X, Y, P, Q))
			r=mid-1;
		else l=mid+1;
	}
	check(n, S, l, X, Y, P, Q);
	return l;
}
// 3 6 2 0 4 1 7 5 
// 1 6 7

Compilation message (stderr)

sorting.cpp: In function 'bool check(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:33:12: warning: declaration of 'j' shadows a previous local [-Wshadow]
   33 |    for(int j=0; j+1<v.size(); j++)
      |            ^
sorting.cpp:25:8: note: shadowed declaration is here
   25 |    int j=cur[i]; used[i]=1;
      |        ^
sorting.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int j=0; j+1<v.size(); j++)
      |                 ~~~^~~~~~~~~
sorting.cpp:37:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |  if(ans.size()>m) return 0;
      |     ~~~~~~~~~~^~
sorting.cpp:44:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(i<ans.size())
      |      ~^~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:56:39: warning: unused parameter 'M' [-Wunused-parameter]
   56 | int findSwapPairs(int n, int S[], 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