Submission #419240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
419240	2021-06-06T15:17:13 Z	JeanBombeur	Sorting (IOI15_sorting)	C++17	100 / 100	378 ms	25120 KB

sorting

#include <iostream>
#include <cstdio>
#include <algorithm>
#include "sorting.h"
using namespace std;
 
//    <|°_°|>
 
const int MAX_ELEMENTS = (600 * 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	9 ms	14284 KB	Output is correct
2	Correct	7 ms	14332 KB	Output is correct
3	Correct	8 ms	14296 KB	Output is correct
4	Correct	7 ms	14284 KB	Output is correct
5	Correct	7 ms	14272 KB	Output is correct
6	Correct	8 ms	14284 KB	Output is correct
7	Correct	7 ms	14284 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14284 KB	Output is correct
2	Correct	7 ms	14332 KB	Output is correct
3	Correct	8 ms	14296 KB	Output is correct
4	Correct	7 ms	14284 KB	Output is correct
5	Correct	7 ms	14272 KB	Output is correct
6	Correct	8 ms	14284 KB	Output is correct
7	Correct	7 ms	14284 KB	Output is correct
8	Correct	8 ms	14284 KB	Output is correct
9	Correct	9 ms	14284 KB	Output is correct
10	Correct	7 ms	14412 KB	Output is correct
11	Correct	9 ms	14364 KB	Output is correct
12	Correct	7 ms	14296 KB	Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14284 KB	Output is correct
2	Correct	7 ms	14332 KB	Output is correct
3	Correct	8 ms	14296 KB	Output is correct
4	Correct	7 ms	14284 KB	Output is correct
5	Correct	7 ms	14272 KB	Output is correct
6	Correct	8 ms	14284 KB	Output is correct
7	Correct	7 ms	14284 KB	Output is correct
8	Correct	8 ms	14284 KB	Output is correct
9	Correct	9 ms	14284 KB	Output is correct
10	Correct	7 ms	14412 KB	Output is correct
11	Correct	9 ms	14364 KB	Output is correct
12	Correct	7 ms	14296 KB	Output is correct
13	Correct	7 ms	14284 KB	Output is correct
14	Correct	7 ms	14284 KB	Output is correct
15	Correct	7 ms	14412 KB	Output is correct
16	Correct	7 ms	14412 KB	Output is correct
17	Correct	8 ms	14412 KB	Output is correct
18	Correct	8 ms	14284 KB	Output is correct
19	Correct	8 ms	14412 KB	Output is correct
20	Correct	8 ms	14284 KB	Output is correct
21	Correct	9 ms	14540 KB	Output is correct
22	Correct	8 ms	14540 KB	Output is correct
23	Correct	10 ms	14484 KB	Output is correct
24	Correct	8 ms	14540 KB	Output is correct
25	Correct	8 ms	14540 KB	Output is correct
26	Correct	9 ms	14540 KB	Output is correct
27	Correct	9 ms	14504 KB	Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14412 KB	Output is correct
2	Correct	9 ms	14412 KB	Output is correct
3	Correct	9 ms	14412 KB	Output is correct
4	Correct	8 ms	14412 KB	Output is correct
5	Correct	9 ms	14340 KB	Output is correct
6	Correct	10 ms	14360 KB	Output is correct
7	Correct	9 ms	14412 KB	Output is correct
8	Correct	11 ms	14412 KB	Output is correct
9	Correct	9 ms	14412 KB	Output is correct
10	Correct	9 ms	14412 KB	Output is correct
11	Correct	9 ms	14412 KB	Output is correct
12	Correct	8 ms	14412 KB	Output is correct
13	Correct	9 ms	14432 KB	Output is correct
14	Correct	8 ms	14412 KB	Output is correct
15	Correct	230 ms	23620 KB	Output is correct
16	Correct	275 ms	23876 KB	Output is correct
17	Correct	362 ms	24516 KB	Output is correct
18	Correct	71 ms	19400 KB	Output is correct
19	Correct	255 ms	23424 KB	Output is correct
20	Correct	294 ms	23776 KB	Output is correct
21	Correct	259 ms	23780 KB	Output is correct
22	Correct	225 ms	24644 KB	Output is correct
23	Correct	272 ms	24960 KB	Output is correct
24	Correct	378 ms	24896 KB	Output is correct
25	Correct	340 ms	24528 KB	Output is correct
26	Correct	267 ms	23748 KB	Output is correct
27	Correct	234 ms	23316 KB	Output is correct
28	Correct	351 ms	24552 KB	Output is correct
29	Correct	315 ms	24332 KB	Output is correct
30	Correct	153 ms	20864 KB	Output is correct
31	Correct	317 ms	24548 KB	Output is correct
32	Correct	270 ms	24472 KB	Output is correct
33	Correct	350 ms	24776 KB	Output is correct
34	Correct	302 ms	24736 KB	Output is correct
35	Correct	238 ms	23236 KB	Output is correct
36	Correct	77 ms	20316 KB	Output is correct
37	Correct	348 ms	25120 KB	Output is correct
38	Correct	335 ms	24568 KB	Output is correct
39	Correct	355 ms	24644 KB	Output is correct

Submission #419240

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0