답안 #71610 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71610	2018-08-25T08:34:18 Z	mr_banana	정렬하기 (IOI15_sorting)	C++17	100 / 100	252 ms	16376 KB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;
const int MN=2e6+100;
int n,a[MN],m,x[MN],y[MN],b[MN];
bool mark[MN];
bool check(int x1){
    for(int i=0;i<n;i++){
        b[i]=a[i];
        mark[i]=0;
    }
    for(int i=0;i<x1;i++){
        swap(b[x[i]],b[y[i]]);
    }
    int cmp=0;
    for(int i=0;i<n;i++){
        if(!mark[i]){
            int x2=i;
            do{
                mark[x2]=1;
                x2=b[x2];
            }while(x2!=i);
            cmp++;
        }
    }
    return (n-cmp)<=x1;
}
int bs(){
    int lo=-1,hi=m;
    while(hi-lo>1){
        int mid=(hi+lo)/2;
        if(check(mid)){
            hi=mid;
        }
        else{
            lo=mid;
        }
    }
    return hi;
}

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];
    }
    m=M;
    for(int i=0;i<m;i++){
        x[i]=X[i],y[i]=Y[i];
    }
    int r=bs();
    for(int i=0;i<n;i++){
        b[i]=a[i];
    }
    for(int i=0;i<r;i++){
        swap(b[x[i]],b[y[i]]);
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        while(b[i]!=i){
            p[cnt]=i;
            q[cnt]=b[i];
            swap(b[i],b[b[i]]);
            cnt++;
        }
    }
    while(cnt<r){
        p[cnt]=0;
        q[cnt]=0;
        cnt++;
    }
    iota(b,b+n,0);
    iota(a,a+n,0);
    for(int i=r-1;i>=0;i--){
        p[i]=a[p[i]];
        q[i]=a[q[i]];
        swap(a[b[x[i]]],a[b[y[i]]]);
        swap(b[x[i]],b[y[i]]);
    }
    return r;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Correct	4 ms	640 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	512 KB	Output is correct
15	Correct	144 ms	13832 KB	Output is correct
16	Correct	159 ms	14108 KB	Output is correct
17	Correct	214 ms	15224 KB	Output is correct
18	Correct	86 ms	11384 KB	Output is correct
19	Correct	131 ms	13916 KB	Output is correct
20	Correct	170 ms	14444 KB	Output is correct
21	Correct	139 ms	14416 KB	Output is correct
22	Correct	171 ms	15096 KB	Output is correct
23	Correct	179 ms	15384 KB	Output is correct
24	Correct	252 ms	15352 KB	Output is correct
25	Correct	245 ms	15608 KB	Output is correct
26	Correct	173 ms	14328 KB	Output is correct
27	Correct	158 ms	13688 KB	Output is correct
28	Correct	235 ms	15100 KB	Output is correct
29	Correct	223 ms	15196 KB	Output is correct
30	Correct	105 ms	13276 KB	Output is correct
31	Correct	210 ms	15608 KB	Output is correct
32	Correct	160 ms	14840 KB	Output is correct
33	Correct	194 ms	15608 KB	Output is correct
34	Correct	184 ms	15308 KB	Output is correct
35	Correct	143 ms	13788 KB	Output is correct
36	Correct	52 ms	12152 KB	Output is correct
37	Correct	201 ms	16376 KB	Output is correct
38	Correct	205 ms	15480 KB	Output is correct
39	Correct	234 ms	15908 KB	Output is correct

답안 #71610

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