제출 #1175844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175844		mertbbm	정렬하기 (IOI15_sorting)	C++20	74 / 100	1095 ms	8592 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++;
	}
	//show(counter,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];
	}
	
	for(int x=0;x<m;x++){
		swap(arr[a[x]],arr[b[x]]);
		//show(count,f());
		if(n-f()<=x+1){
			//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;
				}
				//show4(v,v);
				for(int i=(int)v.size()-2;i>=0;i--){
					int temp=v.back();
					int temp2=v[i];
					//show2(temp,temp,temp2,temp2);
					swap(pos[arr2[a[ptr]]],pos[arr2[b[ptr]]]);
					swap(arr2[a[ptr]],arr2[b[ptr]]);
					//for(int j=0;j<n;j++){
						//cout << arr2[j] << " ";
					//}
					//cout << "\n";
					//for(int j=0;j<n;j++){
						//cout << pos[arr2[j]] << " ";
					//}
					//cout << "\n";
					p[ptr]=pos[temp];
					q[ptr]=pos[temp2];
					swap(pos[arr2[p[ptr]]],pos[arr2[q[ptr]]]);
					swap(arr2[p[ptr]],arr2[q[ptr]]);
					//for(int j=0;j<n;j++){
						//cout << arr2[j] << " ";
					//}
					//cout << "\n";
					//for(int j=0;j<n;j++){
						//cout << pos[arr2[j]] << " ";
					//}
					//cout << "\n";
					ptr++;
				}
			}
			while(ptr<x+1){
				p[ptr]=q[ptr]=0;
				ptr++;
			}
			return x+1;
		}
	}
	return 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