Submission #91286

#	Time	Username	Problem	Language	Result	Execution time	Memory
91286		faustaadp	Sorting (IOI15_sorting)	C++17	100 / 100	423 ms	27228 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,pos[202020],a[202020],n,j,xo[602020],yo[602020];
bool sor()
{
    ll ii;
    for(ii=0;ii<n;ii++)if(a[ii]!=ii)return 0;
    return 1;
}
ll te=0;
ll mir[202020],m;
ll Pmir[202020],ta,tb,taa,tbb,P[202020];
ll cari(ll aa)
{
    if(P[aa]==aa)return aa;
    else
    {
        ll temp=cari(P[aa]);
        P[aa]=temp;
        return P[aa];
    }
}
ll bisa(ll aa)
{
    ll ii,H=0;
    for(ii=0;ii<n;ii++)P[ii]=ii;
    for(ii=0;ii<aa;ii++)
    {
        swap(a[xo[ii]],a[yo[ii]]);
        pos[a[xo[ii]]]=xo[ii];
        pos[a[yo[ii]]]=yo[ii];
    }
    for(ii=0;ii<n;ii++)
    {
        //cout<<i<<" "<<ii<<" "<<a[ii]<<"\n";
        ta=ii;
        tb=a[ii];
        taa=cari(ta);
        tbb=cari(tb);
        if(taa!=tbb)
        {
            H++;
            P[taa]=tbb;
        }
    }
    return (aa>=H);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    for(i=0;i<M;i++)xo[i]=X[i];
    for(i=0;i<M;i++)yo[i]=Y[i];
    for(j=0;j<N;j++)a[j]=S[j];
    for(j=0;j<N;j++)pos[S[j]]=j;
    if(sor())return 0;
    ll L=1,R=N,C;
    while(L<=R)
    {
        C=(L+R)/2;
        for(j=0;j<N;j++)a[j]=S[j];
        for(j=0;j<N;j++)pos[S[j]]=j;
        ll O=bisa(C);
        if(O)
        {
            m=C;
            R=C-1;
        }
        else
            L=C+1;
    }
   // cout<<"M"<<m<<"\n";
    for(j=0;j<N;j++)pos[S[j]]=j;
    for(j=0;j<N;j++)a[j]=S[j];
    for(i=0;i<N;i++)mir[i]=i;
    for(i=m-2;i>=0;i--) swap(mir[X[i+1]],mir[Y[i+1]]);
    for(j=0;j<N;j++)  Pmir[mir[j]]=j;
    te=0;
    for(i=0;i<m;i++)
    {
        swap(a[X[i]],a[Y[i]]);
        pos[a[X[i]]]=X[i];
        pos[a[Y[i]]]=Y[i];
        while(te<=n&&Pmir[te]==pos[te])te++;
        if(te>n)
        {
            P[i]=0;
            Q[i]=0;
        }
        else
        {
            P[i]=Pmir[te];
            Q[i]=pos[te];
            swap(a[P[i]],a[Q[i]]);
            pos[a[P[i]]]=P[i];
            pos[a[Q[i]]]=Q[i];
        }
        if(i<(m-1))
        {
            swap(mir[X[i+1]],mir[Y[i+1]]);
            Pmir[mir[X[i+1]]]=X[i+1];
            Pmir[mir[Y[i+1]]]=Y[i+1];
        }
    }

    return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:54:76: warning: declaration of 'P' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:18:31: note: shadowed declaration is here
 ll Pmir[202020],ta,tb,taa,tbb,P[202020];
                               ^
sorting.cpp:96:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             P[i]=Pmir[te];
                  ~~~~~~~^
sorting.cpp:97:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             Q[i]=pos[te];
                  ~~~~~~^
sorting.cpp:110:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return m;
            ^

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