Submission #135439

#	Time	Username	Problem	Language	Result	Execution time	Memory
135439		TuGSGeReL	Sorting (IOI15_sorting)	C++17	20 / 100	3 ms	632 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int aiz[200001], n, x[600001], y[600001], s[200001], dta[200001];
vector <pii> ans;

bool can(int k)
{
	ans.clear();
	
	for (int i = 0; i < n; i++)
		aiz[i] = s[i];
		
	for (int i = 0; i < k; i++)
		swap(aiz[x[i]], aiz[y[i]]);
	
	for (int i = 0; i < n; i++)
		dta[aiz[i]] = i;
	
	int p = 0;
	
	for (int i = 0; i < n; i++)
	{
		if ( dta[i] != i )
		{
			int tm = aiz[i];
			p++;
			ans.pub(mp(dta[i], dta[tm]));
			swap(aiz[dta[i]], aiz[dta[tm]]);
			swap(dta[i], dta[tm]);
		}
	}
	
	if ( p <= k )
		return 1;
	
	return 0;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l = 0, r = M;
	n = N;
	
	for (int i = 0; i < M; i++)
	{
		x[i] = X[i];
		y[i] = Y[i];
	}
	
	for (int i = 0; i < n; i++)
		s[i] = S[i];
	
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		
		if ( can(mid) )
			r = mid;
		
		else
			l = mid;
	}

	if ( can(l) )
	{
		for (int i = 0; i < ans.size(); i++)
		{
			P[i] = ans[i].ff;
			Q[i] = ans[i].ss;
		}
		
		return l;
	} else {
		can(r);
		
		for (int i = 0; i < ans.size(); i++)
		{
			P[i] = ans[i].ff;
			Q[i] = ans[i].ss;
		}
		
		return r;
	}
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); i++)
                   ~~^~~~~~~~~~~~
sorting.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); i++)
                   ~~^~~~~~~~~~~~

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