oj.uz

Submission #921905

# Submission time Handle Problem Language Result Execution time Memory
921905 2024-02-04T13:33:55 Z coding_snorlax Sorting (IOI15_sorting) C++14
20 / 100
 3 ms 604 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;
    }
    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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 408 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 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 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 2 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 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 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 2 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -