Submission #795730

#	Time	Username	Problem	Language	Result	Execution time	Memory
795730		Username4132	Sorting (IOI15_sorting)	C++14	100 / 100	152 ms	14208 KiB

sorting

#include "sorting.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

int n, cur;

vector<pii> gen(vector<int>& p){
	vector<int> q(n);
	forn(i, n) q[i]=p[i];
	vector<pii> ret;
	vector<bool> vis(n, false);
	forn(i, n) if(!vis[i]){
		vis[i]=true;
		int x=p[i];
		while(x!=i){
			vis[x]=true;
			ret.PB({q[i], q[x]});
			swap(q[i], q[x]);
			x=p[x];
		}
	}
	return ret;
}

void mov(vector<int>& per, int* X, int* Y, int pos){
	while(cur<pos){
		swap(per[X[cur]], per[Y[cur]]);
		++cur;
	}
	while(cur>pos){
		--cur;
		swap(per[X[cur]], per[Y[cur]]);
	}
}

int findSwapPairs(int N, int seq[], int M, int X[], int Y[], int P[], int Q[]) {
	n=N;
	vector<int> per(n);
	forn(i, n) per[i]=seq[i];

	mov(per, X, Y, 3);
	int lo=-1, hi=n;
	while(hi-lo>1){
		int mid = (hi+lo)/2;
		mov(per, X, Y, mid);
		vector<pii> res = gen(per);
		if(res.size()>mid) lo=mid;
		else hi=mid;
	}

	mov(per, X, Y, hi);
	vector<pii> res = gen(per);
	int ans = res.size();
	vector<int> inv(n);
	forn(i, n) inv[seq[i]]=i;

	forn(i, ans){
		int a = res[i].F, b = res[i].S;
		swap(inv[seq[X[i]]], inv[seq[Y[i]]]);
		swap(seq[X[i]], seq[Y[i]]);
		P[i]=inv[a], Q[i]=inv[b];
		swap(seq[P[i]], seq[Q[i]]);
		swap(inv[a], inv[b]);
	}
	forsn(i, ans, hi) P[i]=Q[i]=0;
	return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:55:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(res.size()>mid) lo=mid;
      |      ~~~~~~~~~~^~~~
sorting.cpp:61:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   61 |  int ans = res.size();
      |            ~~~~~~~~^~
sorting.cpp:44:41: warning: unused parameter 'M' [-Wunused-parameter]
   44 | int findSwapPairs(int N, int seq[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                     ~~~~^

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