Submission #36912

#	Time	Username	Problem	Language	Result	Execution time	Memory
36912		moonrabbit2	Sorting (IOI15_sorting)	C++11	100 / 100	239 ms	13304 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int a[N],pl[N];
int fp[N],fq[N];
bool visit[N];
int findSwapPairs(int n,int arr[],int mm,int x[],int y[],int p[],int q[]){
    int s=1,e=n-1,ans=n-1;
    bool issort=true;
    for(int i=0;i<n;i++)
        if(arr[i]!=i)
            issort=false;
    if(issort)
        return 0;
    while(s<=e){
        for(int i=0;i<n;i++)
            a[i]=arr[i],pl[i]=i,visit[i]=false;
        int m=(s+e)/2,res=0;
        for(int i=0;i<m;i++)
            swap(a[x[i]],a[y[i]]);
        for(int i=0;i<n;i++)
            pl[a[i]]=i;
        for(int i=0;i<n;i++){
            if(visit[i])
                continue;
            int curr=i,amt=1;
            visit[i]=true;
            while(pl[curr]!=i){
                //un(curr,pl[curr]);
                curr=pl[curr];
                visit[curr]=true;
                amt++;
            }
            res+=amt-1;
        }
        if(res<=m){
            e=m-1;
            ans=m;
        }
        else
            s=m+1;
    }
    for(int i=0;i<n;i++)
        a[i]=arr[i];
    int res=0,cp=0;
    for(int i=0;i<n;i++)
        pl[a[i]]=i;
    for(int i=0;i<ans;i++)
        swap(a[x[i]],a[y[i]]);
    for(int i=0;i<ans;i++){
        while(cp<n&&cp==a[cp])
            cp++;
        if(cp<n){
            fp[i]=a[cp],fq[i]=a[a[cp]];
            swap(a[cp],a[a[cp]]);
        }
        else{
            fp[i]=fq[i]=1;
        }
    }
    for(int i=0;i<n;i++)
        a[i]=arr[i];
    for(int i=0;i<ans;i++){
        swap(pl[a[x[i]]],pl[a[y[i]]]);
        swap(a[x[i]],a[y[i]]);
        p[i]=pl[fp[i]],q[i]=pl[fq[i]];
        swap(pl[fp[i]],pl[fq[i]]);
        swap(a[pl[fp[i]]],a[pl[fq[i]]]);
    }
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:46:9: warning: unused variable 'res' [-Wunused-variable]
     int res=0,cp=0;
         ^~~
sorting.cpp:8:39: warning: unused parameter 'mm' [-Wunused-parameter]
 int findSwapPairs(int n,int arr[],int mm,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: 26 / 26