oj.uz

Submission #419238

# Submission time Handle Problem Language Result Execution time Memory
419238 2021-06-06T15:16:00 Z JeanBombeur Sorting (IOI15_sorting) C++17
74 / 100
 63 ms 19712 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4900 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4900 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4900 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 5 ms 5068 KB Output is correct
24 Correct 5 ms 5196 KB Output is correct
25 Correct 4 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 4 ms 5068 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 5 ms 4940 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 5 ms 4940 KB Output is correct
15 Runtime error 63 ms 19712 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -