Submission #921989

#	Time	Username	Problem	Language	Result	Execution time	Memory
921989		coding_snorlax	Sorting (IOI15_sorting)	C++14	74 / 100	33 ms	10324 KiB

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> in_queue;
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){
    while((int)in_queue.size()){
        int i = *in_queue.begin();
        in_queue.erase(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++) in_queue.insert(i);
    for(int i=0;i<N;i++){
        inv_S[S[i]]=i;
    }
    for(int i=0;i<L;i++){
        if(in_queue.find(X[i])!=in_queue.end() && in_queue.find(Y[i])==in_queue.end()){
            in_queue.insert(Y[i]);
            in_queue.erase(X[i]);
        }
        else if(in_queue.find(Y[i])!=in_queue.end() && in_queue.find(X[i])==in_queue.end()){
            in_queue.insert(X[i]);
            in_queue.erase(Y[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;
        find_Sol(P,Q,S,i);
    }
	return L;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:58:39: warning: unused parameter 'M' [-Wunused-parameter]
   58 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

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