Submission #91241

#	Time	Username	Problem	Language	Result	Execution time	Memory
91241		faustaadp	Sorting (IOI15_sorting)	C++17	0 / 100	1063 ms	6924 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,x[202020],y[202020];
bool sor()
{
    ll ii;
    for(ii=0;ii<n;ii++)
        if(pos[ii]!=ii)return 0;
    return 1;
}
ll te=0;
ll mir[15005][505];
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];
        //cout<<X[i+1]<<" "<<Y[i+1]<<"\n";
        swap(mir[ii][x[ii+1]],mir[ii][y[ii+1]]);
        for(jj=0;jj<n;jj++)
            Pmir[ii][mir[ii][jj]]=jj;
    }
    for(ii=0;ii<aa;ii++)
    {
        swap(a[x[ii]],a[y[ii]]);
        pos[a[x[ii]]]=x[ii];
        pos[a[y[ii]]]=y[ii];
        ll ax=Pmir[ii][ii];
        ll bx=pos[ii];
        swap(a[ax],a[bx]);
        pos[a[ax]]=a[ax];
        pos[a[bx]]=a[bx];
    }
    //cout<<aa<<" "<<sor()<<"\n";
    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++)x[i]=X[i];
    for(i=0;i<M;i++)y[i]=Y[i];
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)pos[S[j]]=j;
        for(j=0;j<N;j++)a[j]=S[j];
        if(bisa(i))
        {
            M=i;
            break;
        }
    }
    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++)
  //      cout<<a[i]<<" ";
  //  cout<<"\n";
    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;
    }
    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];
        P[i]=Pmir[i][i];
        Q[i]=pos[i];
        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];
    }
    return M;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:58:15: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             M=i;
               ^
sorting.cpp:78:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         if(sor())return i;
                         ^
sorting.cpp:82:23: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         P[i]=Pmir[i][i];
              ~~~~~~~~~^
sorting.cpp:83:19: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         Q[i]=pos[i];
              ~~~~~^

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