Submission #712086

#	Time	Username	Problem	Language	Result	Execution time	Memory
712086		ToroTN	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	0 ms	340 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
int n,m,arr[2005][2005],brr[2005][2005],ans=2e9;
void rotate()
{
    //printf("%d %d\n",n,m);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            brr[i][j]=arr[n-j+1][i];
        }
    }
    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)arr[i][j]=brr[i][j];
    swap(n,m);
}
void cal()
{
    int st=1,md,ed=1e9;
    while(ed>=st)
    {
        md=(st+ed)/2;
        int bnd=m,mx=-2e9,mn=2e9,mn2=2e9,mx2=-2e9,type=0;
        //printf("%d %d %d\n",st,md,ed);
        for(int i=1;i<=n;i++)
        {
            type=0;
            for(int j=1;j<=bnd;j++)
            {
                if(arr[i][j]>md)
                {
                    bnd=j-1;
                    for(int k=j;k<=m;k++)
                    {
                        mn2=min(mn2,arr[i][k]);
                        mx2=max(mx2,arr[i][k]);
                    }
                    type=-1;
                    break;
                }else   
                {
                    mn=min(mn,arr[i][j]),mx=max(mx,arr[i][j]);
                }
            }
            if(type==0)
            {
                for(int j=bnd+1;j<=m;j++)
                {
                    mn2=min(mn2,arr[i][j]);
                    mx2=max(mx2,arr[i][j]);
                }
            }
        }
        //printf("%d %d %d %d\n",mx,mn,mx2,mn2);
        if(mx==-2e9&&mn==2e9)
        {
            st=md+1;
        }else if(mx2==-2e9&&mn2==2e9)
        {
            ed=md-1;
        }else
        {
            if(mx-mn<mx2-mn2)
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
    }
    int bnd=m,mx=-2e9,mn=2e9,mn2=2e9,mx2=-2e9,type=0;
    for(int i=1;i<=n;i++)
    {
        type=0;
        for(int j=1;j<=bnd;j++)
        {
            if(arr[i][j]>st)
            {
                bnd=j-1;
                //printf("%d %d\n",i,bnd);
                for(int k=j;k<=m;k++)
                {
                    mn2=min(mn2,arr[i][k]);
                    mx2=max(mx2,arr[i][k]);
                }
                type=-1;
                break;
            }else   
            {
                mn=min(mn,arr[i][j]),mx=max(mx,arr[i][j]);
            }
        }
        if(type==0)
        {
            for(int j=bnd+1;j<=m;j++)
            {
                mn2=min(mn2,arr[i][j]);
                mx2=max(mx2,arr[i][j]);
            }
        }
    }
    ans=min(ans,mx-mn);
    --st;
    bnd=m,mx=-2e9,mn=2e9,mn2=2e9,mx2=-2e9,type=0;
    for(int i=1;i<=n;i++)
    {
        type=0;
        for(int j=1;j<=bnd;j++)
        {
            if(arr[i][j]>st)
            {
                bnd=j-1;
                //printf("%d %d\n",i,bnd);
                for(int k=j;k<=m;k++)
                {
                    mn2=min(mn2,arr[i][k]);
                    mx2=max(mx2,arr[i][k]);
                }
                type=-1;
                break;
            }else   
            {
                mn=min(mn,arr[i][j]),mx=max(mx,arr[i][j]);
            }
        }
        if(type==0)
        {
            for(int j=bnd+1;j<=m;j++)
            {
                mn2=min(mn2,arr[i][j]);
                mx2=max(mx2,arr[i][j]);
            }
        }
    }
    ans=min(ans,mx2-mn2);
}
void debug()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)printf("%d ",arr[i][j]);
        printf("\n");
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&arr[i][j]);
    //cal();
    rotate();
    //cal();
    rotate();
    cal();
    rotate();
    //cal();
    printf("%d\n",ans);
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joioi.cpp:149:52: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&arr[i][j]);
      |                                               ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40