oj.uz

Submission #921937

# Submission time Handle Problem Language Result Execution time Memory
921937 2024-02-04T14:31:13 Z coding_snorlax Sorting (IOI15_sorting) C++14
74 / 100
 42 ms 18048 KB 
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int Answer[10000],vis[10000],Goal[10000];
int n;
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){
    for(int i=0;i<n;i++){
        if(S[i]!=Answer[i]){
            for(int j=0;j<n;j++){
                if(S[j]==Answer[i]){
                    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<L;i++){
        int tmp = S[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:56:39: warning: unused parameter 'M' [-Wunused-parameter]
   56 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 516 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 440 KB Output is correct
14 Correct 1 ms 504 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 576 KB Output is correct
22 Correct 1 ms 572 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 4 ms 516 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 1 ms 344 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 4 ms 516 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Runtime error 42 ms 18048 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -