제출 #1226120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226120		abdelhakim	Sorting (IOI15_sorting)	C++20	0 / 100	7 ms	580 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' <<x << endl;
#define ll long long
using namespace std;
vector<ll> ind;
vector<ll> dest;
vector<ll> recip;
vector<ll> s;
void swp(ll i, ll j)
{
	swap(s[i],s[j]);
	ind[s[i]]=i;
	ind[s[j]]=j;
	swap(dest[s[i]],dest[s[j]]);
	recip[dest[s[i]]]=ind[s[i]];
	recip[dest[s[j]]]=ind[s[j]];
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;
	ind.resize(N);
	dest.resize(N);
	recip.resize(N);
	for (int i=0;i<N;i++)
	{
		s.push_back(S[i]);
	}
	for (int i=0;i<N;i++)
	{
		ind[s[i]]=i;
		ll cur=i;
		for (int j=0;j<M;j++)
		{
			if(cur==X[j])
			{
				cur=Y[j];
			}
			else if(cur==Y[j])
			{
				cur=X[j];
			}
		}
		dest[s[i]]=cur;
		recip[cur]=i;
	}
	ll cur=0;
	for (int i=0;i<M;i++)
	{
		swap(s[X[i]],s[Y[i]]);
		ind[s[X[i]]]=X[i];
		ind[s[X[i]]]=Y[i];
		swap(recip[dest[s[X[i]]]],recip[dest[s[Y[i]]]]);
		if(cur==N)
		{
			P[i]=0;
			Q[i]=0;
		}
		else
		{
			for (;cur<N;cur++)
			{
				if(dest[cur]!=cur)
				{
					P[i]=ind[cur];
					Q[i]=recip[cur];
					swp(P[i],Q[i]);
					cur++;
					break;
				}
			}
			if(cur==N)
			{
				P[i]=0;
				Q[i]=0;
			}
		}
	}
	return M;
}

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