제출 #91249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91249		faustaadp	정렬하기 (IOI15_sorting)	C++17	74 / 100	1087 ms	11356 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[2020],m;
ll Pmir[2020];
bool bisa(ll aa)
{
    ll ii,jj;
    for(ii=0;ii<n;ii++)mir[ii]=ii;
    for(ii=0;ii<n;ii++)Pmir[ii]=ii;
    for(ii=aa-2;ii>=0;ii--)
        swap(mir[xo[ii+1]],mir[yo[ii+1]]);
    for(jj=0;jj<n;jj++)  Pmir[mir[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[te]==pos[te])te++;
        if(te<=n)
        {
            ll ax=Pmir[te];
            ll bx=pos[te];
            swap(a[ax],a[bx]);
            pos[a[ax]]=ax;
            pos[a[bx]]=bx;
        }
        if(ii<(aa-1))
        {
            swap(mir[xo[ii+1]],mir[yo[ii+1]]);
            Pmir[mir[xo[ii+1]]]=xo[ii+1];
            Pmir[mir[yo[ii+1]]]=yo[ii+1];
        }
    }
    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;
    for(i=1;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++)mir[i]=i;
    for(i=0;i<N;i++)Pmir[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++)
    {
        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[te]==pos[te])te++;
        if(te>n)
        {
            P[i]=0;
            Q[i]=0;
        }
        else
        {
            P[i]=Pmir[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];
        }
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:79:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         if(sor())return i;
                         ^
sorting.cpp:91:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             P[i]=Pmir[te];
                  ~~~~~~~^
sorting.cpp:92:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             Q[i]=pos[te];
                  ~~~~~~^
sorting.cpp:106: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: 0 / 26