Submission #135935

#	Time	Username	Problem	Language	Result	Execution time	Memory
135935		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(i, 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 < n; i++)
			aiz[i] = s[i];
    	
		for(int i = 0 ; i < n; i++)
			dta[aiz[i]] = i;
    	
		for(int i = 0; i < l; i++)
    	{
    		swap(aiz[x[i]], aiz[y[i]]);
    		swap(dta[aiz[x[i]]],dta[aiz[y[i]]]);
    		P[i] = dta[ans[i].ff];
    		Q[i] = dta[ans[i].ss];
			swap(aiz[dta[ans[i].ff]],aiz[dta[ans[i].ss]]);
			swap(dta[ans[i].ff],dta[ans[i].ss]);
    	}
		
		return l;
	} else {
		can(r);
		
		for (int i = 0; i < n; i++)
			aiz[i] = s[i];
    	
		for(int i = 0 ; i < n; i++)
			dta[aiz[i]] = i;
    	
		for(int i = 0; i < r; i++)
    	{
    		swap(aiz[x[i]], aiz[y[i]]);
    		swap(dta[aiz[x[i]]],dta[aiz[y[i]]]);
    		P[i] = dta[ans[i].ff];
    		Q[i] = dta[ans[i].ss];
			swap(aiz[dta[ans[i].ff]],aiz[dta[ans[i].ss]]);
			swap(dta[ans[i].ff],dta[ans[i].ss]);
    	}
		
		return r;
	}
}

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