Submission #140562

#	Time	Username	Problem	Language	Result	Execution time	Memory
140562		SirCeness	Sorting (IOI15_sorting)	C++14	74 / 100	1083 ms	11080 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x) "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

int n, m;

int dene(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	n = N; m = M;
	vector<int> sanal;
	for (int i = 0; i < n; i++) sanal.pb(S[i]);
	for (int i = 0; i < m; i++) swap(sanal[X[i]], sanal[Y[i]]);
	
	vector<int> sim;
	for (int i = 0; i < n; i++) sim.pb(S[i]);
	
	//prarrv(sanal);
	
	vector<int> yer(n);
	for (int i = 0; i < n; i++) yer[sanal[i]] = i;
	
	vector<pair<int, int> > deg;
	for (int i = 0; i < n; i++){
		if (sanal[i] != i){
			int j = yer[i];
			yer[sanal[i]] = j;
			deg.pb(mp(sanal[i], sanal[j]));
			swap(sanal[i], sanal[j]);
		}
	}
	
	//for (int i = 0; i < deg.size(); i++) cout << ppair(deg[i]) << " "; cout << endl;
	
	int r = deg.size();
	if (r > m) return 0; 
	return 1;
}

void yap(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
	n = N; m = M;
	vector<int> sanal;
	for (int i = 0; i < n; i++) sanal.pb(S[i]);
	for (int i = 0; i < m; i++) swap(sanal[X[i]], sanal[Y[i]]);
	
	vector<int> sim;
	for (int i = 0; i < n; i++) sim.pb(S[i]);
	
	//prarrv(sanal);
	vector<int> yer(n);
	for (int i = 0; i < n; i++) yer[sanal[i]] = i;
	
	vector<pair<int, int> > deg;
	for (int i = 0; i < n; i++){
		if (sanal[i] != i){
			int j = yer[i];
			yer[sanal[i]] = j;
			deg.pb(mp(sanal[i], sanal[j]));
			swap(sanal[i], sanal[j]);
		}
	}
	
	//for (int i = 0; i < deg.size(); i++) cout << ppair(deg[i]) << " "; cout << endl;
	
	int r = deg.size();
	//if (r > m) return 0;
	
	for (int i = 0; i < n; i++) yer[S[i]] = i;
	
	for (int i = 0; i < M; i++){
		yer[S[X[i]]] = Y[i];
		yer[S[Y[i]]] = X[i];
		swap(S[X[i]], S[Y[i]]);
		if (i >= r){
			P[i] = 0;
			Q[i] = 0;
			continue;
		}
		P[i] = yer[deg[i].first];
		Q[i] = yer[deg[i].second];
		for (int j = 0; j < n; j++){
			if (S[j] == deg[i].first) P[i] = j;
			if (S[j] == deg[i].second) Q[i] = j;
		}
		yer[S[P[i]]] = Q[i];
		yer[S[Q[i]]] = P[i];
		swap(S[P[i]], S[Q[i]]);
	}
	
	/*prarrv(sim);
	for (int i = 0; i < m; i++){
		swap(sim[X[i]], sim[Y[i]]);
		prarrv(sim);
		swap(sim[P[i]], sim[Q[i]]);
		prarrv(sim);
	}*/
	
	//return 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l = 0;
	int r = M;
	while (l < r){
		int mid = (l+r)/2;
		if (dene(N, S, mid, X, Y, P, Q)) r = mid;
		else l = mid+1;
	}
	yap(N, S, l, X, Y, P, Q);
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int dene(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:46:18: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int r = deg.size();
          ~~~~~~~~^~
sorting.cpp:20:57: warning: unused parameter 'P' [-Wunused-parameter]
 int dene(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
                                                         ^
sorting.cpp:20:66: warning: unused parameter 'Q' [-Wunused-parameter]
 int dene(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
                                                                  ^
sorting.cpp: In function 'void yap(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:76:18: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int r = deg.size();
          ~~~~~~~~^~

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