Submission #329164

#	Time	Username	Problem	Language	Result	Execution time	Memory
329164		arnold518	Sorting (IOI15_sorting)	C++14	0 / 100	3 ms	620 KiB

sorting

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 6e5;

int N, M, ans;
int S[MAXN+10], X[MAXN+10], Y[MAXN+10], *P, *Q;
int A[MAXN+10], B[MAXN+10], T[MAXN+10];
bool vis[MAXN+10];

bool solve(int R)
{	
	for(int i=1; i<=N; i++) A[i]=S[i];
	for(int i=1; i<=R; i++)
	{
		swap(A[X[i]], A[Y[i]]);
	}

	vector<pii> V;
	for(int i=1; i<=N; i++) vis[i]=false;

	//for(int i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
	for(int i=1; i<=N; i++)
	{
		if(vis[i]) continue;
		for(int now=i; ; now=A[now])
		{
			vis[now]=true;
			if(vis[A[now]]) break;
			V.push_back({A[now], A[A[now]]});
			//printf("!%d %d\n", A[now], A[A[now]]);
		}
	}
	if(V.size()>R) return false;

	for(int i=1; i<=N; i++) T[i]=i, A[i]=i;
	for(int i=1; i<=R; i++) P[i]=Q[i]=1;
	for(int i=R; i>=1; i--)
	{
		//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");
		if(!V.empty())
		{
			pii t=V.back(); V.pop_back();
			pii a=pii(T[t.first], T[t.second]);
			P[i]=a.first; Q[i]=a.second;
			swap(A[a.first], A[a.second]);
			swap(T[t.first], T[t.second]);
		}

		//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");

		pii a=pii(X[i], Y[i]);
		pii t=pii(A[a.first], A[a.second]);
		swap(A[a.first], A[a.second]);
		swap(T[t.first], T[t.second]);
	}

	for(int i=0; i<R; i++)
	{
		P[i]=P[i+1]-1;
		Q[i]=Q[i+1]-1;
	}
	return true;
}

int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[])
{
	N=_N; M=_M; P=_P; Q=_Q;
	for(int i=1; i<=N; i++) S[i]=_S[i-1]+1;
	for(int i=1; i<=M; i++) X[i]=_X[i-1]+1, Y[i]=_Y[i-1]+1;

	solve(M);
	return M;
}

Compilation message (stderr)

sorting.cpp: In function 'bool solve(int)':
sorting.cpp:39:13: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  if(V.size()>R) return false;
      |     ~~~~~~~~^~

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