Submission #221805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
221805	2020-04-11T07:56:40 Z	patrikpavic2	Sorting (IOI15_sorting)	C++17	100 / 100	494 ms	33956 KB

sorting

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  sorting
* score: 100.0
* date:  2019-06-23 09:06:27.945005
*/
#include "sorting.h"
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue> 
#include <algorithm>

using namespace std;

const int N = 1e6 + 500;

int E[N], EE[N], P[N], Q[N], S[N], SSS[N], X[N], Y[N], n;
queue < int > q;

bool check(int m){
	for(int i = 0;i < n;i++) S[i] = SSS[i];
	for(int i = 0;i < n;i++) EE[i] = i, E[i] = i;
    for(int i = m - 1;i >= 0;i--) {
    	swap(E[EE[X[i]]], E[EE[Y[i]]]);
    	swap(EE[X[i]], EE[Y[i]]);
    }
    for(int i = 0;i < n;i++){
   		q.push(i);
    }
    for(int i = 0;i < m;i++){
    	swap(S[X[i]], S[Y[i]]);
       	swap(EE[X[i]], EE[Y[i]]);
    	swap(E[EE[X[i]]], E[EE[Y[i]]]);
    	if(X[i] != E[S[X[i]]]) q.push(X[i]);
    	if(Y[i] != E[S[Y[i]]]) q.push(Y[i]);
    	P[i] = 0, Q[i] = 0;
    	for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
    	if(!q.empty()) P[i] = q.front(), Q[i] = E[S[q.front()]];
    	swap(S[P[i]], S[Q[i]]);
    }
    for(;!q.empty() && q.front() == E[S[q.front()]]; q.pop());
    return q.empty();
}

int findSwapPairs(int nn, int SS[], int M, int XX[], int YY[], int PP[], int QQ[]) {
	n = nn;
	for(int i = 0;i < M;i++) X[i] = XX[i], Y[i] = YY[i];
	for(int i = 0;i < n;i++) SSS[i] = SS[i];
	int ans = -1;
	for(int i = 20;i >= 0;i--){
		if(ans + (1 << i) <= M && !check(ans + (1 << i)))
			ans += (1 << i);
	}
	check(ans + 1);
	for(int i = 0;i <= ans;i++)  
		PP[i] = P[i], QQ[i] = Q[i];
	return ans + 1;
}

Subtask #1

8.0 / 8.0

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

Subtask #2

12.0 / 12.0

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

Subtask #3

16.0 / 16.0

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

Subtask #4

18.0 / 18.0

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

Subtask #5

20.0 / 20.0

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

Subtask #6

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	640 KB	Output is correct
2	Correct	6 ms	768 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	5 ms	640 KB	Output is correct
5	Correct	6 ms	640 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	6 ms	640 KB	Output is correct
8	Correct	6 ms	640 KB	Output is correct
9	Correct	6 ms	896 KB	Output is correct
10	Correct	6 ms	768 KB	Output is correct
11	Correct	6 ms	640 KB	Output is correct
12	Correct	7 ms	640 KB	Output is correct
13	Correct	7 ms	640 KB	Output is correct
14	Correct	6 ms	640 KB	Output is correct
15	Correct	309 ms	30728 KB	Output is correct
16	Correct	374 ms	29080 KB	Output is correct
17	Correct	459 ms	32412 KB	Output is correct
18	Correct	147 ms	26360 KB	Output is correct
19	Correct	311 ms	28916 KB	Output is correct
20	Correct	322 ms	29476 KB	Output is correct
21	Correct	326 ms	29708 KB	Output is correct
22	Correct	298 ms	29972 KB	Output is correct
23	Correct	324 ms	32416 KB	Output is correct
24	Correct	464 ms	33912 KB	Output is correct
25	Correct	457 ms	33524 KB	Output is correct
26	Correct	298 ms	30632 KB	Output is correct
27	Correct	267 ms	28836 KB	Output is correct
28	Correct	468 ms	31880 KB	Output is correct
29	Correct	440 ms	31452 KB	Output is correct
30	Correct	212 ms	28272 KB	Output is correct
31	Correct	436 ms	31672 KB	Output is correct
32	Correct	335 ms	33308 KB	Output is correct
33	Correct	494 ms	33956 KB	Output is correct
34	Correct	390 ms	33692 KB	Output is correct
35	Correct	319 ms	28808 KB	Output is correct
36	Correct	103 ms	27768 KB	Output is correct
37	Correct	476 ms	31708 KB	Output is correct
38	Correct	449 ms	30784 KB	Output is correct
39	Correct	481 ms	32920 KB	Output is correct