Submission #1243470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243470		moondarkside	Sorting (IOI15_sorting)	C++20	74 / 100	1096 ms	7356 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]);
                
                int a=BaseSequence[P[RS]];
                BaseSequence[P[RS]]=BaseSequence[Q[RS]];
                BaseSequence[Q[RS]]=a;
                
                
                base=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(NewS)==0){
        return 0;
    }
    
    int i=0;
    while(true){
        int a=NewS[X[i]];
        NewS[X[i]]=NewS[Y[i]];
        NewS[Y[i]]=a;
        i++;
        if(GetReqMoves(NewS)<=i){
            int moves = DoMoves(GetReqSeq(NewS),BaseSequence,P,Q,X,Y);
            for(int j=moves;j<i;j++){
                P[j]=0;
                Q[j]=0;
            }
            return i;
        }
        
    }
    return i;
    
}

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