Submission #137832

#	Time	Username	Problem	Language	Result	Execution time	Memory
137832		dolphingarlic	Sorting (IOI15_sorting)	C++14	100 / 100	651 ms	28280 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 6e5+9;
int n,m,x[inf],y[inf],a[inf],pos[inf],from[inf],origin[inf],posfrom[inf];
 
bool check(int i,int p[],int q[]){
 
        int l = 0,notvalid = 0;
        for(int j=0;j<n;j++){
            from[j] = j;
            a[j] = origin[j];
            p[j] = q[j] = 0;
            pos[ a[j] ] = j;
            posfrom[ from[j] ] = j;
            notvalid += (a[j] != j);
        }
        //cout<<i<<" "<<notvalid<<endl;
         for(int j=i;j>=0;j--){
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
            swap( from[ x[j] ] , from[ y[j] ] );
        }
 
        for(int j=0;j<=i;j++){
 
            swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
 
            notvalid -= (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(a[ x[j] ] , a[ y[j] ] );
            notvalid += (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(from[ x[j] ] , from[ y[j] ]);
 
            //cout<<notvalid<<" ";
            int idx,idfrom;
 
            while(l<n){
                idx = pos[l];
                idfrom = posfrom[l];
                if(idx != idfrom)
                    break;
                l++;
            }
            swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
            notvalid -= (a[idx] != idx) + (a[idfrom] != idfrom);
            swap(a[idx],a[idfrom]);
            notvalid += (a[idx] != idx) + (a[idfrom] != idfrom);
 
            //cout<<notvalid<<" ";
            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            //cout<<"swap "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
            if(notvalid == 0)
                return 1;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        return 0;
}
 
int findSwapPairs(int N, int A[], int M, int X[], int Y[], int p[], int q[]){
    n = N;
    m = M;
    bool tr = 1;
    for(int i=0;i<n;i++){
        a[i] = A[i];
        pos[ a[i] ] = i;
        origin[i] = a[i];
        if(a[i] != i)
            tr = 0;
    }
    if(tr)
        return 0;
 
    for(int i=0;i<m;i++)
        x[i] = X[i],y[i] = Y[i];
 
    int l = 0 , r = m-1;
    while(r-l>1){
        if(check(mid,p,q))
            r = mid;
        else
            l = mid;
    }
    if(check(0,p,q))
        r = 0;
    check(r,p,q);
    return r+1;
}

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