답안 #1090933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090933	2024-09-19T08:03:18 Z	owoovo	정렬하기 (IOI15_sorting)	C++17	0 / 100	1 ms	604 KB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int tar[200010],tarp[200010],n,x[200010],y[200010],s[200010];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N;
	for(int i=0;i<M;i++){
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	int l=0,r=M;
	while(l!=r){
		int m=(l+r)>>1,ok=1;
		//cout<<l<<" "<<r<<" "<<m<<"\n";
		for(int i=0;i<N;i++){
			tar[i]=i;
			s[i]=S[i];
		}
		for(int i=m;i>0;i--){
			swap(tar[x[i]],tar[y[i]]);
		}
		for(int i=0;i<N;i++){
			tarp[tar[i]]=i;
		}
		int ans=0;
		if(m!=0){
			swap(tarp[tar[x[1]]],tarp[tar[y[1]]]);
			swap(tar[x[1]],tar[y[1]]);
			swap(s[x[1]],s[y[1]]);
		}
		for(int i=0;i<N;i++){
			if(s[i]==tar[i])continue;
			int now=tarp[s[i]],ori=i;
			while(now!=ori){
				P[ans]=now;
				Q[ans]=ori;
				swap(s[now],s[ori]);
				ans++;
				if(ans>=m)break;
				if(ori==x[ans+1]||ori==y[ans+1])ori^=x[ans+1]^y[ans+1];
				if(now==x[ans+1]||now==y[ans+1])now^=x[ans+1]^y[ans+1];
				swap(tarp[tar[x[ans+1]]],tarp[tar[y[ans+1]]]);
				swap(tar[x[ans+1]],tar[y[ans+1]]);
				swap(s[x[ans+1]],s[y[ans+1]]);
				now=tarp[s[ori]];
			}
			if(ans>=m)break;
		}
		for(int i=0;i<n;i++){
			//cout<<s[i]<<" "<<tar[i]<<"\n";
			if(s[i]!=tar[i])ok=0;
		}
		if(ok==0){
			l=m+1;
		}else{
			r=m;
		}
	}

	int m=l;
	for(int i=0;i<N;i++){
		tar[i]=i;
		s[i]=S[i];
	}
	for(int i=m;i>0;i--){
		swap(tar[x[i]],tar[y[i]]);
	}
	for(int i=0;i<N;i++){	
		tarp[tar[i]]=i;
	}
	int ans=0;
	if(m!=0){
		swap(tarp[tar[x[1]]],tarp[tar[y[1]]]);
		swap(tar[x[1]],tar[y[1]]);
		swap(s[x[1]],s[y[1]]);
	}
	for(int i=0;i<N;i++){
		if(s[i]==tar[i])continue;
		int now=tarp[s[i]],ori=i;
		while(now!=ori){
			P[ans]=now;
			Q[ans]=ori;
			swap(s[now],s[ori]);
			ans++;
			if(ans>=m)break;
			if(ori==x[ans+1]||ori==y[ans+1])ori^=x[ans+1]^y[ans+1];
			if(now==x[ans+1]||now==y[ans+1])now^=x[ans+1]^y[ans+1];
			swap(tarp[tar[x[ans+1]]],tarp[tar[y[ans+1]]]);
			swap(tar[x[ans+1]],tar[y[ans+1]]);
			swap(s[x[ans+1]],s[y[ans+1]]);
			now=tarp[s[ori]];
		}
		if(ans>=m)break;
	}
	return l;
}

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Incorrect	0 ms	348 KB	Output isn't correct
7	Halted	0 ms	0 KB	-