Submission #754932

#	Time	Username	Problem	Language	Result	Execution time	Memory
754932		APROHACK	Sorting (IOI15_sorting)	C++14	16 / 100	2 ms	340 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
vector<int>arr;
vector<int>whereIs[2];
vector<int>current;
void cambiar(vector<int>&v, int i, int j){
	int temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;
	vector<int>copia;
	bool valid = true;
	for(int i = 0 ; i < N ; i ++){
		whereIs[0].pb(0);
		whereIs[1].pb(0);
		if(S[i] != i)valid = false;
	}
	if(valid)return 0;
	for(int i = 0 ; i < N ; i ++){
		copia.pb(S[i]);
		current.pb(S[i]);
		arr.pb(S[i]);
		whereIs[0][S[i]] = i;
		whereIs[1][S[i]] = i;
		
	}
	for(int i = 0 ; i < N ; i ++){
		cambiar(copia, X[i], Y[i]);
		//for(auto j : copia) cout << j << " " ;
		//cout << endl;
	}
	for(int i = 0 ; i < N ; i ++){
		//cout << "donde esta " << copia[i] << " = " << whereIs[copia[i]] << endl;
		arr[whereIs[0][copia[i]]] = i;
	}
	for(int i  = 0 ; i < N ; i ++){
		whereIs[0][arr[i]] = i;
	}
	int currentC = 0;
	int i = 0;
	while(currentC < N){
		cambiar(arr, X[i], Y[i]);
		whereIs[0][arr[X[i]]] = X[i];
		whereIs[0][arr[Y[i]]] = Y[i];
		cambiar(current, X[i], Y[i]);
		whereIs[1][current[X[i]]] = X[i];
		whereIs[1][current[Y[i]]] = Y[i];
		while(currentC < N and whereIs[1][currentC] == whereIs[0][currentC])currentC++;
		if(currentC >= N)break;
		P[i] = whereIs[1][currentC];
		Q[i] = whereIs[0][currentC];
		cambiar(current, P[i], Q[i]);
		whereIs[1][current[P[i]]] = P[i];
		whereIs[1][current[Q[i]]] = Q[i];
		i++;
		currentC++;
	}
	
	//for(auto k : current)cout << k << " " << endl;
	return N;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:16:39: warning: unused parameter 'M' [-Wunused-parameter]
   16 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

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