답안 #921990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921990	2024-02-04T16:01:49 Z	coding_snorlax	정렬하기 (IOI15_sorting)	C++14	100 / 100	303 ms	31828 KB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int Answer[200005],vis[200005],Goal[200005],inv_S[200005];
int n;
set<int> in_queue;
int Count_cycle(int S[]){
    for(int i=0;i<n;i++){
        vis[i]=0;
    }
    for(int i=0;i<n;i++){
        Goal[S[i]]=Answer[i];
    }
    int answer = n;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            vis[i]=1;
            int st = i,now = i;
            while(Goal[now]!=st){
                now = Goal[now];
                vis[now]=1;
            }
            answer-=1;
        }
    }
    return answer;
}
void find_Sol(int P[],int Q[],int S[],int ope){
    while((int)in_queue.size()){
        int i = *in_queue.begin();
        in_queue.erase(i);
        if(S[i]!=Answer[i]){
            int j = inv_S[Answer[i]];
            inv_S[S[j]]=i;
            inv_S[S[i]]=j;
            P[ope]=i;
            Q[ope]=j;
            S[j]=S[i];
            S[i]=Answer[i];
            return;
        }
    }
    P[ope]=0;Q[ope]=0;
}
int Check(int k,int S[],int X[],int Y[]){
    for(int i=0;i<n;i++){
        Answer[i]=i;
    }
    for(int i=k-1;i>=0;i--){
        int tmp  = Answer[X[i]];
        Answer[X[i]]=Answer[Y[i]];
        Answer[Y[i]]=tmp;
    }
    if(Count_cycle(S)<=k) return 1;
    else return 0;
 
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    int L = 0,R = N;
    while(L!=R){
        int m = (L+R)/2;
        if(Check(m,S,X,Y)) R=m;
        else L=m+1;
    }
    Check(L,S,X,Y);
    for(int i=0;i<n;i++) in_queue.insert(i);
    for(int i=0;i<N;i++){
        inv_S[S[i]]=i;
    }
    for(int i=0;i<L;i++){
        if(in_queue.find(X[i])!=in_queue.end() && in_queue.find(Y[i])==in_queue.end()){
            in_queue.insert(Y[i]);
            in_queue.erase(X[i]);
        }
        else if(in_queue.find(Y[i])!=in_queue.end() && in_queue.find(X[i])==in_queue.end()){
            in_queue.insert(X[i]);
            in_queue.erase(Y[i]);
        }
        int tmp = S[X[i]];
        inv_S[S[X[i]]]=Y[i];
        inv_S[S[Y[i]]]=X[i];
        S[X[i]]=S[Y[i]];
        S[Y[i]]=tmp;
        tmp  = Answer[X[i]];
        Answer[X[i]]=Answer[Y[i]];
        Answer[Y[i]]=tmp;
        find_Sol(P,Q,S,i);
    }
	return L;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:58:39: warning: unused parameter 'M' [-Wunused-parameter]
   58 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2660 KB	Output is correct
2	Correct	2 ms	2648 KB	Output is correct
3	Correct	2 ms	2652 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	1 ms	2652 KB	Output is correct
6	Correct	1 ms	2652 KB	Output is correct
7	Correct	2 ms	2652 KB	Output is correct
8	Correct	2 ms	2652 KB	Output is correct
9	Correct	2 ms	2652 KB	Output is correct
10	Correct	2 ms	2652 KB	Output is correct
11	Correct	2 ms	2648 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	2 ms	2652 KB	Output is correct
14	Correct	1 ms	2652 KB	Output is correct
15	Correct	157 ms	20112 KB	Output is correct
16	Correct	201 ms	29780 KB	Output is correct
17	Correct	285 ms	29712 KB	Output is correct
18	Correct	80 ms	25172 KB	Output is correct
19	Correct	188 ms	28572 KB	Output is correct
20	Correct	208 ms	29256 KB	Output is correct
21	Correct	214 ms	29232 KB	Output is correct
22	Correct	151 ms	26708 KB	Output is correct
23	Correct	187 ms	31056 KB	Output is correct
24	Correct	262 ms	30568 KB	Output is correct
25	Correct	303 ms	31828 KB	Output is correct
26	Correct	213 ms	29296 KB	Output is correct
27	Correct	188 ms	28312 KB	Output is correct
28	Correct	251 ms	30480 KB	Output is correct
29	Correct	251 ms	29800 KB	Output is correct
30	Correct	149 ms	27808 KB	Output is correct
31	Correct	258 ms	31692 KB	Output is correct
32	Correct	197 ms	30036 KB	Output is correct
33	Correct	261 ms	30528 KB	Output is correct
34	Correct	215 ms	31612 KB	Output is correct
35	Correct	220 ms	28100 KB	Output is correct
36	Correct	94 ms	26820 KB	Output is correct
37	Correct	268 ms	31272 KB	Output is correct
38	Correct	268 ms	30104 KB	Output is correct
39	Correct	268 ms	30380 KB	Output is correct

답안 #921990

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