Submission #91248

#	Time	Username	Problem	Language	Result	Execution time	Memory
91248		faustaadp	Sorting (IOI15_sorting)	C++17	20 / 100	118 ms	29448 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[202020],yo[202020];
bool sor()
{
    ll ii;
    for(ii=0;ii<n;ii++)
        if(a[ii]!=ii)return 0;
    return 1;
}
ll te=0;
ll mir[15005][505],m;
ll Pmir[15005][505];
bool bisa(ll aa)
{
    ll ii,jj;
    for(ii=0;ii<n;ii++)mir[aa-1][ii]=ii;
    for(ii=0;ii<n;ii++)Pmir[aa-1][ii]=ii;
    for(ii=aa-2;ii>=0;ii--)
    {
        for(jj=0;jj<n;jj++)mir[ii][jj]=mir[ii+1][jj];
        swap(mir[ii][xo[ii+1]],mir[ii][yo[ii+1]]);
        for(jj=0;jj<n;jj++)
            Pmir[ii][mir[ii][jj]]=jj;
    }
    te=0;
    for(ii=0;ii<aa;ii++)
    {
        if(sor())return 1;
        swap(a[xo[ii]],a[yo[ii]]);
        pos[a[xo[ii]]]=xo[ii];
        pos[a[yo[ii]]]=yo[ii];
        while(te<=n&&Pmir[ii][te]==pos[te])te++;
        if(te>n)continue;
        ll ax=Pmir[ii][te];
        ll bx=pos[te];
        swap(a[ax],a[bx]);
        pos[a[ax]]=ax;
        pos[a[bx]]=bx;
    }
    return sor();
}
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];
    m=-1;
    ll L=1;
    ll R=N;
    ll C;
    while(L<=R)
    {
        C=(L+R)/2;
        for(j=0;j<N;j++)pos[S[j]]=j;
        for(j=0;j<N;j++)a[j]=S[j];
        if(bisa(C))
        {
            m=i;
            R=C-1;
        }
        else
            L=C+1;
    }
    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[m-1][i]=i;
    for(i=0;i<N;i++)Pmir[m-1][i]=i;
    for(i=m-2;i>=0;i--)
    {
        for(j=0;j<N;j++)mir[i][j]=mir[i+1][j];
        swap(mir[i][X[i+1]],mir[i][Y[i+1]]);
        for(j=0;j<N;j++)
            Pmir[i][mir[i][j]]=j;
    }
    te=0;
    for(i=0;i<m;i++)
    {
        if(sor())return i;
        swap(a[X[i]],a[Y[i]]);
        pos[a[X[i]]]=X[i];
        pos[a[Y[i]]]=Y[i];
        while(te<=n&&Pmir[i][te]==pos[te])te++;
        if(te>n)
        {
            P[i]=0;
            Q[i]=0;
            continue;
        }
        P[i]=Pmir[i][te];
        Q[i]=pos[te];
        if(P[i]>Q[i])swap(P[i],Q[i]);
        swap(a[P[i]],a[Q[i]]);
        pos[a[P[i]]]=P[i];
        pos[a[Q[i]]]=Q[i];
    }
    //cout<<sor()<<"\n";
    return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:85:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         if(sor())return i;
                         ^
sorting.cpp:96:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         P[i]=Pmir[i][te];
              ~~~~~~~~~~^
sorting.cpp:97:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         Q[i]=pos[te];
              ~~~~~~^
sorting.cpp:104: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: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26