Submission #419238

#	Time	Username	Problem	Language	Result	Execution time	Memory
419238		JeanBombeur	Sorting (IOI15_sorting)	C++17	74 / 100	63 ms	19712 KiB

sorting

#include <iostream>
#include <cstdio>
#include <algorithm>
#include "sorting.h"
using namespace std;

//    <|°_°|>

const int MAX_ELEMENTS = (200 * 1000);
const int LOG = (20);

int findSwapPairs(int nbElements, int Depart[], int nbEchanges, int Premier[], int Deuxieme[], int AnsPremier[], int AnsDeuxieme[]) {
	
	int IndiceArrivant[MAX_ELEMENTS];
	
	int Arrivee[MAX_ELEMENTS];
	int ValeurAct[MAX_ELEMENTS];
	int IndexCourant[MAX_ELEMENTS];
	
	pair <int, int> ReponseAct[MAX_ELEMENTS];
	
    int nbMin = nbEchanges + 1;

	for (int add = (1 << LOG); add > 0; add /= 2)
	{
	    int testCur = max(0, nbMin - add);
	    for (int i = 0; i < nbElements; i ++)
	    {
	        Arrivee[i] = i;
	        ValeurAct[i] = Depart[i];
	        IndexCourant[Depart[i]] = i;
	    }
	    for (int i = testCur - 1; i >= 0; i --)
	    {
	        swap(Arrivee[Premier[i]], Arrivee[Deuxieme[i]]);
	    }
	    for (int i = 0; i < nbElements; i ++)
	    {
	        IndiceArrivant[Arrivee[i]] = i;
	    }

	    int premierPasBon = 0;
	    
	    for (int i = 0; i < testCur; i ++)
	    {
	        int a = Premier[i], b = Deuxieme[i];
	        swap(IndexCourant[ValeurAct[a]], IndexCourant[ValeurAct[b]]);
	        swap(IndiceArrivant[Arrivee[a]], IndiceArrivant[Arrivee[b]]);
            swap(Arrivee[a], Arrivee[b]);
	        swap(ValeurAct[a], ValeurAct[b]);
	        
	        while (premierPasBon < nbElements && Arrivee[IndexCourant[premierPasBon]] == premierPasBon)
	        {
	            premierPasBon ++;
	        }
	        if (premierPasBon == nbElements)
	        {
	            ReponseAct[i] = {0, 0};
	        }
	        else
	        {
	            int c = IndexCourant[premierPasBon];
	            int d = IndiceArrivant[premierPasBon];
	            ReponseAct[i] = {c, d};
	            swap(IndexCourant[ValeurAct[c]], IndexCourant[ValeurAct[d]]);
	            swap(ValeurAct[c], ValeurAct[d]);
	        }
	    }
	    while (premierPasBon < nbElements && Arrivee[IndexCourant[premierPasBon]] == premierPasBon)
	    {
	        premierPasBon ++;
	    }
	    if (premierPasBon == nbElements)
	    {
	        nbMin = testCur;
	        for (int i = 0; i < nbMin; i ++)
	        {
	            AnsPremier[i] = ReponseAct[i].first;
	            AnsDeuxieme[i] = ReponseAct[i].second;
	        }
	    }
	}
	return nbMin;
}

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