답안 #311811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311811	2020-10-11T19:34:53 Z	hhh07	정렬하기 (IOI15_sorting)	C++14	100 / 100	465 ms	24312 KB

sorting

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include "sorting.h"

using namespace std;


int moze(int n, int s[], int m, int x[], int y[], int p[], int q[]){
    int pos[n], s_copy[n], s_copy2[n];
    
    for (int i = 0; i < n; i++)
        pos[s[i]] = i, s_copy[i] = s[i], s_copy2[i] = s[i];
    
    for (int i = 0; i < m; i++)
        swap(s[x[i]], s[y[i]]);
    
    int kraj_pos[n];
    for (int i = 0; i < n; i++)
        kraj_pos[s[i]] = i;
    
    int f[n], g[n];
    for (int i = 0; i < n; i++){
        f[i] = kraj_pos[s_copy[i]];
        g[kraj_pos[s_copy[i]]] = i;
    }
    
    int cnt = 0;
    for (int i = 0; i < m; i++){
        swap(f[x[i]], f[y[i]]);
        g[f[x[i]]] = x[i]; g[f[y[i]]] = y[i];
        
        swap(s_copy2[x[i]], s_copy2[y[i]]);
        pos[s_copy2[x[i]]] = x[i]; pos[s_copy2[y[i]]] = y[i];
        
        bool t = false;
        while(cnt < n){
            int idx = g[cnt];
            
            if (s_copy2[idx] != cnt){
                int a = idx, b = pos[cnt];
                swap(s_copy2[a], s_copy2[b]);
                p[i] = a; q[i] = b;
                pos[s_copy2[a]] = a; pos[s_copy2[b]] = b;
                t = true;
                break;
            }
            cnt++;
        }
        
        if (!t)
            p[i] = q[i] = 0;
        else
            cnt++;
    }
    for (int i = 0; i < n; i++)
        s[i] = s_copy[i];

    for (int i = 0; i < n; i++){
        if (s_copy2[i] != i)
            return false;
    }
    
    return true;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int beg = 0, end = m;
    
    while(beg < end){
        int mid = (beg + end)/2;
        for (int i = 0; i < n; i++)
            p[i] = 0, q[i] = 0;
        if (moze(n, s, mid, x, y, p, q))
            end = mid;
        else
            beg = mid + 1;
    }
    
    if (moze(n, s, beg, x, y, p, q))
        return beg;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	2 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	1 ms	512 KB	Output is correct
15	Correct	320 ms	21368 KB	Output is correct
16	Correct	369 ms	22008 KB	Output is correct
17	Correct	451 ms	23160 KB	Output is correct
18	Correct	138 ms	19960 KB	Output is correct
19	Correct	292 ms	22404 KB	Output is correct
20	Correct	309 ms	23032 KB	Output is correct
21	Correct	309 ms	23032 KB	Output is correct
22	Correct	330 ms	18424 KB	Output is correct
23	Correct	386 ms	24056 KB	Output is correct
24	Correct	465 ms	23800 KB	Output is correct
25	Correct	448 ms	23320 KB	Output is correct
26	Correct	360 ms	23032 KB	Output is correct
27	Correct	330 ms	22392 KB	Output is correct
28	Correct	430 ms	23544 KB	Output is correct
29	Correct	415 ms	23032 KB	Output is correct
30	Correct	269 ms	22008 KB	Output is correct
31	Correct	434 ms	23672 KB	Output is correct
32	Correct	361 ms	23160 KB	Output is correct
33	Correct	464 ms	23672 KB	Output is correct
34	Correct	411 ms	23672 KB	Output is correct
35	Correct	298 ms	22136 KB	Output is correct
36	Correct	120 ms	21368 KB	Output is correct
37	Correct	420 ms	24312 KB	Output is correct
38	Correct	395 ms	23416 KB	Output is correct
39	Correct	400 ms	23544 KB	Output is correct

답안 #311811

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