Submission #921978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921978	2024-02-04T15:41:53 Z	coding_snorlax	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int Answer[10000],vis[10000],Goal[10000],inv_S[10000];
int n;
set<int> OK;
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]){
            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++){
        inv_S[S[i]]=i;
    }
    for(int i=0;i<L;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;
        debug();
        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:77:9: error: 'debug' was not declared in this scope
   77 |         debug();
      |         ^~~~~
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[]) {
      |                                   ~~~~^