Submission #590882

#	Time	Username	Problem	Language	Result	Execution time	Memory
590882		FatihSolak	Sorting (IOI15_sorting)	C++17	74 / 100	1051 ms	17144 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool ck(int n,int s[],int m,int x[],int y[]){
	if(is_sorted(s,s+n))
		return 1;
	vector<int> fnal;
	vector<int> now;
	vector<int> pfnal(n,0);
	vector<int> pnow(n,0);
	int cnt = 0;
	for(int i = 0;i<n;i++){
		fnal.push_back(s[i]);
		pfnal[s[i]] = i;
		now.push_back(s[i]);
		pnow[s[i]] = i;
		cnt += (s[i] == i);
	}
	for(int i = 0;i<m;i++){
		swap(pfnal[fnal[x[i]]],pfnal[fnal[y[i]]]);
		swap(fnal[x[i]],fnal[y[i]]);
	}
	int num = 0;
	for(int i = 0;i<m;i++){
		if(pnow[now[x[i]]] == now[x[i]])cnt--;
		if(pnow[now[y[i]]] == now[y[i]])cnt--;
		swap(now[x[i]],now[y[i]]);
		swap(pnow[now[x[i]]],pnow[now[y[i]]]);
		if(pnow[now[x[i]]] == now[x[i]])cnt++;
		if(pnow[now[y[i]]] == now[y[i]])cnt++;
		while(num < n){
			int ps1 = pnow[num];
			int ps2 = pnow[fnal[num]];
			if(ps1 == ps2){
				num++;
				continue;
			}
			if(pnow[now[ps1]] == now[ps1])cnt--;
			if(pnow[now[ps2]] == now[ps2])cnt--;
			swap(pnow[now[ps1]],pnow[now[ps2]]);
			swap(now[ps1],now[ps2]);
			if(pnow[now[ps1]] == now[ps1])cnt++;
			if(pnow[now[ps2]] == now[ps2])cnt++;
			int tmp = pfnal[num];
			swap(pfnal[fnal[num]],pfnal[num]);
			swap(fnal[num],fnal[tmp]);
			num++;
			break;
		}
		if(cnt == n)
			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;
	while(l < r){
		int mm = (l + r)/2;
		if(ck(n,s,mm,x,y)){
			r = mm;
		}
		else l = mm+1;
	}
	m = l;*/
	for(int i = n;i>=1;i--){
		if(ck(n,s,i,x,y)){
			m = i;
		}
	}
	if(is_sorted(s,s+n))
		return 0;
	for(int i = 0;i<m;i++){
		p[i] = q[i] = 0;
	}
	vector<int> fnal;
	vector<int> now;
	vector<int> pfnal(n,0);
	vector<int> pnow(n,0);
	int cnt = 0;
	for(int i = 0;i<n;i++){
		fnal.push_back(s[i]);
		pfnal[s[i]] = i;
		now.push_back(s[i]);
		pnow[s[i]] = i;
		cnt += (s[i] == i);
	}
	for(int i = 0;i<m;i++){
		swap(pfnal[fnal[x[i]]],pfnal[fnal[y[i]]]);
		swap(fnal[x[i]],fnal[y[i]]);
	}
	int num = 0;
	for(int i = 0;i<m;i++){
		if(pnow[now[x[i]]] == now[x[i]])cnt--;
		if(pnow[now[y[i]]] == now[y[i]])cnt--;
		swap(now[x[i]],now[y[i]]);
		swap(pnow[now[x[i]]],pnow[now[y[i]]]);
		if(pnow[now[x[i]]] == now[x[i]])cnt++;
		if(pnow[now[y[i]]] == now[y[i]])cnt++;
		while(num < n){
			int ps1 = pnow[num];
			int ps2 = pnow[fnal[num]];
			if(ps1 == ps2){
				num++;
				continue;
			}
			p[i] = ps1;
			q[i] = ps2;
			if(pnow[now[ps1]] == now[ps1])cnt--;
			if(pnow[now[ps2]] == now[ps2])cnt--;
			swap(pnow[now[ps1]],pnow[now[ps2]]);
			swap(now[ps1],now[ps2]);
			if(pnow[now[ps1]] == now[ps1])cnt++;
			if(pnow[now[ps2]] == now[ps2])cnt++;
			int tmp = pfnal[num];
			swap(pfnal[fnal[num]],pfnal[num]);
			swap(fnal[num],fnal[tmp]);
			num++;
			break;
		}
		if(cnt == n)
			return i+1;
	}
	assert(0);
}

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