제출 #1243228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243228		moondarkside	정렬하기 (IOI15_sorting)	C++20	20 / 100	17 ms	328 KiB

sorting

#include<bits/stdc++.h>
using namespace std;

int GetReqMoves(vector<int> Base){
    int a=0;
    vector<bool> Visited(Base.size(),false);
    for(int i=0;i<Base.size();i++){
        if(Visited[i]==false){
            a++;
            Visited[i]=true;
            int j=Base[i];
            while(j!=i){
                Visited[j]=true;
                j=Base[j];
            }
        }
    }
    return Base.size()-a;
}

vector<vector<int>> GetReqSeq(vector<int> Base){
    int a=0;
    vector<vector<int>> Ret;
    vector<bool> Visited(Base.size(),false);
    for(int i=0;i<Base.size();i++){
        
        if(Visited[i]==false){
            vector<int> Seq;
            a++;
            Visited[i]=true;
            Seq.push_back(Base[i]);
            int j=Base[i];
            
            while(j!=i){
                Visited[j]=true;
                Seq.push_back(Base[j]);
                j=Base[j];
            }
            Ret.push_back(Seq);
        }
    }
    return Ret;
}

int getIndex(vector<int> BaseSequence,int t){
    for(int i=0;i<BaseSequence.size();i++){
        if(BaseSequence[i]==t){
            return i;
        }
    }
    return 0;
    
}

int DoMoves(vector<vector<int>> Seq, vector<int> BaseSequence,int* P, int* Q,int* X,int* Y){
    int swaps=0;
    int temp=BaseSequence[X[swaps]];
    BaseSequence[X[swaps]]=BaseSequence[Y[swaps]];
    BaseSequence[Y[swaps]]=temp;
    swaps++;
    
    int RS=0;
    
    for(int i=0;i<Seq.size();i++){
        if(Seq[i].size()>1){
            int base=Seq[i][0];
            for(int j=1;j<Seq[i].size();j++){
                P[RS]=getIndex(BaseSequence,base);
                Q[RS]=getIndex(BaseSequence,Seq[i][j]);
                
                RS++;
                
                int temp2=BaseSequence[X[swaps]];
                BaseSequence[X[swaps]]=BaseSequence[Y[swaps]];
                BaseSequence[Y[swaps]]=temp2;
                swaps++;
                
            }
        }
        
    }
    return RS;
}

int findSwapPairs(int N,int* S,int  M,int* X,int* Y,int* P,int* Q){
    vector<int> BaseSequence;
    for(int i=0;i<N;i++){
        BaseSequence.push_back(S[i]);
    }
    
    std::vector<int> NewS=BaseSequence;
    
    if(GetReqMoves(BaseSequence)==0){
        return 0;
    }
    
    int i=0;
    while(true){
        int a=NewS[X[i]];
        NewS[X[i]]=NewS[Y[i]];
        NewS[Y[i]]=a;
        if(GetReqMoves(NewS)==i){
            return DoMoves(GetReqSeq(NewS),BaseSequence,P,Q,X,Y);
        }
        
        if(GetReqMoves(NewS)<i){
            P[i]=0;
            Q[i]=0;
            return DoMoves(GetReqSeq(NewS),BaseSequence,P,Q,X,Y)+1;
        }
        
        i++;
    }
    
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26