답안 #419217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419217	2021-06-06T14:52:46 Z	someone	정렬하기 (IOI15_sorting)	C++14	100 / 100	209 ms	25752 KB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
//#define int long long
using namespace std;

const int N = 2e5 + 10, M = N * 3;

int n, a[N], b[N], s[M][2], pos[N];

int dicho(int deb, int fin) {
    if(deb + 1 == fin)
        return deb;
    int med = (deb + fin) / 2 - 1;
    for(int i = 0; i < n; i++)
        b[i] = a[i];
    for(int i = 0; i < med; i++)
        swap(b[s[i][0]], b[s[i][1]]);
    int t = 0;
    for(int i = 0; i < n; i++) {
        while(b[i] != i) {
            t++;
            swap(b[i], b[b[i]]);
        }
    }
    if(t <= med)
        return dicho(deb, med+1);
    return dicho(med+1, fin);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    for(int i = 0; i < n; i++)
        a[i] = S[i];
    for(int i = 0; i < M; i++) {
        s[i][0] = X[i];
        s[i][1] = Y[i];
    }
    int etape = dicho(0, M);
    for(int i = 0; i < etape; i++)
        P[i] = Q[i] = 0;
    for(int i = 0; i < n; i++)
        b[i] = a[i];
    for(int i = 0; i < etape; i++)
        swap(b[s[i][0]], b[s[i][1]]);
    for(int i = 0; i < n; i++)
        pos[a[i]] = i;

    int j = 0;
    for(int i = 0; i < n; i++) {
        while(b[i] != i) {
            swap(pos[a[s[j][0]]], pos[a[s[j][1]]]);
            swap(a[s[j][0]], a[s[j][1]]);
            P[j] = pos[b[i]];
            Q[j] = pos[b[b[i]]];
            swap(pos[b[i]], pos[b[b[i]]]);
            swap(a[pos[b[i]]], a[pos[b[b[i]]]]);
            swap(b[i], b[b[i]]);
            j++;
        }
    }
    return etape;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:30:39: warning: declaration of 'M' shadows a global declaration [-Wshadow]
   30 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^
sorting.cpp:6:25: note: shadowed declaration is here
    6 | const int N = 2e5 + 10, M = N * 3;
      |                         ^
sorting.cpp:30:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   30 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:6:11: note: shadowed declaration is here
    6 | const int N = 2e5 + 10, M = N * 3;
      |           ^

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	256 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	2 ms	588 KB	Output is correct
22	Correct	2 ms	588 KB	Output is correct
23	Correct	2 ms	592 KB	Output is correct
24	Correct	2 ms	608 KB	Output is correct
25	Correct	2 ms	588 KB	Output is correct
26	Correct	2 ms	588 KB	Output is correct
27	Correct	2 ms	568 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	436 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	420 KB	Output is correct
13	Correct	2 ms	444 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	1 ms	436 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	420 KB	Output is correct
13	Correct	2 ms	444 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	153 ms	21932 KB	Output is correct
16	Correct	174 ms	22416 KB	Output is correct
17	Correct	183 ms	24120 KB	Output is correct
18	Correct	72 ms	19880 KB	Output is correct
19	Correct	127 ms	22968 KB	Output is correct
20	Correct	140 ms	23604 KB	Output is correct
21	Correct	145 ms	23748 KB	Output is correct
22	Correct	148 ms	18948 KB	Output is correct
23	Correct	180 ms	24536 KB	Output is correct
24	Correct	185 ms	24496 KB	Output is correct
25	Correct	209 ms	24424 KB	Output is correct
26	Correct	132 ms	23568 KB	Output is correct
27	Correct	117 ms	22832 KB	Output is correct
28	Correct	188 ms	24064 KB	Output is correct
29	Correct	170 ms	24228 KB	Output is correct
30	Correct	88 ms	22340 KB	Output is correct
31	Correct	175 ms	24688 KB	Output is correct
32	Correct	190 ms	23664 KB	Output is correct
33	Correct	189 ms	24700 KB	Output is correct
34	Correct	185 ms	24316 KB	Output is correct
35	Correct	132 ms	22660 KB	Output is correct
36	Correct	54 ms	21256 KB	Output is correct
37	Correct	209 ms	25752 KB	Output is correct
38	Correct	206 ms	24388 KB	Output is correct
39	Correct	188 ms	24896 KB	Output is correct

답안 #419217

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