Submission #812304

#	Time	Username	Problem	Language	Result	Execution time	Memory
812304		LIF	Sorting (IOI15_sorting)	C++14	100 / 100	139 ms	28516 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int a[300005];
vector<pair<int,int> > last;
int pos[300005];
int AA[300005][2];
int val[300005][2];
vector<pair<int,int> > pp;
bool check(int now,int X[],int Y[],int N,int S[])
{
	for(int i=0;i<N;i++)a[i] = S[i];
	for(int i=0;i<now;i++)swap(a[X[i]],a[Y[i]]);
	for(int i=0;i<N;i++)pos[a[i]] = i;
	int ans = 0;
	vector<pair<int,int> > temp;
	for(int i=0;i<N;i++)
	{
		if(a[i] == i)continue;
		int aa = i;
		int bb = pos[i];
		swap(a[aa],a[bb]);
		pos[a[bb]] = bb;
		temp.push_back(make_pair(aa,bb));
		ans++;
	}
	if(temp.size() > now)return false;
	if(temp.size() < now)for(int i=1;i<= now-temp.size();i++)temp.push_back(make_pair(0,0));
	if(ans <= now)
	{
		pp = temp;
		return true;
	}
	else return false;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	for(int i=0;i<N;i++)a[i] = S[i];
 	int needtime = 0;
	int l = 0;
	int r = M;
	while(l <= r)
	{
		int mid = (l+r)>>1;
		if(check(mid,X,Y,N,S) == true)
		{
			r = mid - 1;
			needtime = mid;
		}
		else l = mid + 1;
	}
	for(int i=0;i<N;i++)
	{
		a[i] = S[i];
		pos[a[i]] = i;
	}
	for(int i=0;i<needtime;i++)last.push_back(make_pair(X[i],Y[i]));
	for(int i=0;i<needtime;i++)last.push_back(pp[i]);
	/*for(int i=0;i<last.size();i++)cout<<last[i].first<<" "<<last[i].second<<endl;
	cout<<endl;*/
	for(int i=needtime;i<needtime*2;i++)
	{
		AA[i-needtime][0] = last[i].first;
		AA[i-needtime][1] = last[i].second;
	}
	for(int i=0;i<needtime;i++)
	{
		swap(a[X[i]],a[Y[i]]);
		swap(pos[a[X[i]]],pos[a[Y[i]]]);
	}
	for(int i=0;i<needtime;i++)// we find all 
	{
		val[i][0] = a[AA[i][0]];
		val[i][1] = a[AA[i][1]];
		swap(a[AA[i][0]],a[AA[i][1]]);
		swap(pos[a[AA[i][0]]],pos[a[AA[i][1]]]);
	}
	for(int i=0;i<N;i++)
	{
		a[i] = S[i];
		pos[a[i]] = i;
	}
	/*for(int i=0;i<needtime;i++)
	{
		cout<<val[i][0]<<" "<<val[i][1]<<endl;
	}
	cout<<endl;*/
	for(int i=0;i<needtime;i++)
	{
		swap(a[X[i]],a[Y[i]]);
		swap(pos[a[X[i]]],pos[a[Y[i]]]);
		
		P[i] = pos[val[i][0]];
		Q[i] = pos[val[i][1]];
		
		swap(a[P[i]],a[Q[i]]);
		swap(pos[a[P[i]]],pos[a[Q[i]]]);
	}
	//test:
	for(int i=0;i<N;i++)a[i] = S[i];
	for(int i=0;i<needtime;i++)
	{
		swap(a[X[i]],a[Y[i]]);
		swap(a[P[i]],a[Q[i]]);
	}
	/*for(int i=0;i<N;i++)cout<<a[i]<<" ";
	cout<<endl;*/
	return needtime;
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int, int*, int*, int, int*)':
sorting.cpp:27:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  if(temp.size() > now)return false;
      |     ~~~~~~~~~~~~^~~~~
sorting.cpp:28:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |  if(temp.size() < now)for(int i=1;i<= now-temp.size();i++)temp.push_back(make_pair(0,0));
      |     ~~~~~~~~~~~~^~~~~
sorting.cpp:28:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  if(temp.size() < now)for(int i=1;i<= now-temp.size();i++)temp.push_back(make_pair(0,0));
      |                                   ~^~~~~~~~~~~~~~~~~~

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