제출 #1222626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222626		HossamHero7	정렬하기 (IOI15_sorting)	C++20	16 / 100	1 ms	580 KiB

sorting

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

int findSwapPairs(int n, int s[], int m, int X[], int Y[], int P[], int Q[]) {
    vector<int> tar(n);
	iota(tar.begin(),tar.end(),0);
	for(int i=0;i<n;i++) P[i] = Q[i] = 0;
	vector<int> tmp(n);
	for(int i=0;i<n;i++) tmp[i] = s[i];
	for(int i=n-1;i>=0;i--){
		swap(tar[X[i]],tar[Y[i]]);
	}
	// for(auto i : tar) cout<<i<<' ';
	// cout<<endl;
	vector<int> idx(n);
	for(int i=0;i<n;i++){
		idx[s[i]] = i;
	}
	set<int> st;
	for(int i=0;i<n;i++){
		if(s[i] != tar[i]) st.insert(i);
	}
	auto do_swap = [&](int i,int j){
		int x = s[i] , y = s[j];
		if(s[i] != tar[i]) st.erase(i);
		if(s[j] != tar[j]) st.erase(j);
		swap(s[i],s[j]);
		swap(idx[x],idx[y]);
		if(s[i] != tar[i]) st.insert(i);
		if(s[j] != tar[j]) st.insert(j);
	};
	int pt = 0;
	// for(auto i : tar) cout<<i<<' ';
	// cout<<endl;
	for(int i=0;i<n;i++){
		do_swap(X[i],Y[i]);
		if(tar[X[i]] != s[X[i]]) st.erase(X[i]);
		if(tar[Y[i]] != s[Y[i]]) st.erase(Y[i]);
		swap(tar[X[i]],tar[Y[i]]);
		if(tar[X[i]] != s[X[i]]) st.insert(X[i]);
		if(tar[Y[i]] != s[Y[i]]) st.insert(Y[i]);
		if(st.size()){
			int pt = *st.begin();
			if(pt != n) P[i] = pt , Q[i] = idx[tar[pt]] , do_swap(pt,idx[tar[pt]]);
		}
	}
	for(int i=0;i<n;i++) {
		swap(tmp[X[i]],tmp[Y[i]]);
		swap(tmp[P[i]],tmp[Q[i]]);
	}
	// for(auto i : tmp) cout<<i<<' ';
	// cout<<endl;
	return n;
}

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