Submission #1175851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175851		mertbbm	Sorting (IOI15_sorting)	C++20	100 / 100	128 ms	14156 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}	
	
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 0;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

int arr[200005];
int n;

int f(){
	DSU dsu;
	dsu.init(n);
	for(int x=0;x<n;x++){
		dsu.unite(x,arr[x]);
	}
	int cnt[n+5];
	memset(cnt,0,sizeof(cnt));
	int counter=0;
	for(int x=0;x<n;x++){
		int hold=dsu.get(x);
		cnt[hold]++;
		if(cnt[hold]==1) counter++;
	}
	return counter;
}

int findSwapPairs(int N, int s[], int m, int a[], int b[], int p[], int q[]){
	n=N;
	int pos[n];
	for(int x=0;x<n;x++){
		arr[x]=s[x];
		pos[arr[x]]=x;
	}
	
	if(f()==n){
		return 0;
	}
	
	int arr2[n];
	for(int x=0;x<n;x++){
		arr2[x]=arr[x];
	}
	
	int l=0;
	int r=m-1;
	int mid;
	int best=r;
	int take=0;
	while(l<=r){
		mid=(l+r)/2;
		while(take<=mid){
			swap(arr[a[take]],arr[b[take]]);
			take++;
		}
		while(take-1>mid){
			take--;
			swap(arr[a[take]],arr[b[take]]);
		}
		if(n-f()<=mid+1){
			best=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	while(take<=best){
		swap(arr[a[take]],arr[b[take]]);
		take++;
	}
	while(take-1>best){
		take--;
		swap(arr[a[take]],arr[b[take]]);
	}

	//answer
	bool visited[n+5];
	memset(visited,0,sizeof(visited));
	int ptr=0;
	for(int y=0;y<n;y++){
		if(visited[y]) continue;
		int cur=y;
		vector<int>v;
		while(1){
			v.push_back(cur);
			visited[cur]=true;
			cur=arr[cur];
			if(cur==y) break;
		}
		for(int i=(int)v.size()-2;i>=0;i--){
			int temp=v.back();
			int temp2=v[i];
			swap(pos[arr2[a[ptr]]],pos[arr2[b[ptr]]]);
			swap(arr2[a[ptr]],arr2[b[ptr]]);
			p[ptr]=pos[temp];
			q[ptr]=pos[temp2];
			swap(pos[arr2[p[ptr]]],pos[arr2[q[ptr]]]);
			swap(arr2[p[ptr]],arr2[q[ptr]]);
			ptr++;
		}
	}
	while(ptr<best+1){
		p[ptr]=q[ptr]=0;
		ptr++;
	}
	return best+1;
}

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