Submission #43688

#	Time	Username	Problem	Language	Result	Execution time	Memory
43688		dqhungdl	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	2 ms	480 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
int X[]={0,0,-1,1};
int Y[]={-1,1,0,0};
int m,n,idi,idj,minn=1e9,a[2005][2005],b[2005][2005];
bool Free[2005][2005];
queue<ii> Q;

void Rotate()
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            b[n-j+1][i]=a[i][j];
    int newidi=n-idj+1;
    int newidj=idi;
    swap(m,n);
    idi=newidi;
    idj=newidj;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=b[i][j];
}

bool Check(int lim)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=idj;j++)
        if(minn+lim<a[idi][j])
            return false;
        else
            Free[idi][j]=true;
    for(int j=idj+1;j<=n;j++)
        if(minn+lim>=a[idi][j])
            Free[idi][j]=true;
        else
            break;
    for(int i=idi-1;i>=1;i--)
    {
        bool check=false;
        for(int j=1;j<=n;j++)
            if(minn+lim>=a[i][j])
            {
                check=true;
                Free[i][j]=true;
            }
            else
                break;
        if(check==false)
            break;
    }
    for(int i=idi+1;i<=m;i++)
    {
        bool check=false;
        for(int j=1;j<=n;j++)
            if(minn+lim>=a[i][j])
            {
                check=true;
                Free[i][j]=true;
            }
            else
                break;
        if(check==false)
            break;
    }
    int leftmost=-1,rightmost=-1;
    for(int i=1;i<=m;i++)
        if(Free[i][n]==false)
        {
            leftmost=i;
            break;
        }
    for(int i=m;i>=1;i--)
        if(Free[i][n]==false)
        {
            rightmost=i;
            break;
        }
    if(leftmost==-1)
        return true;
    int nmin=1e9,nmax=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<n;j++)
            if(Free[i][j]==false)
            {
                nmin=min(nmin,a[i][j]);
                nmax=max(nmax,a[i][j]);
            }
    int premin=nmin,premax=nmax;
    for(int i=1;i<=rightmost;i++)
    {
        nmin=min(nmin,a[i][n]);
        nmax=max(nmax,a[i][n]);
    }
    if(nmax-nmin<=lim)
        return true;
    nmin=premin;
    nmax=premax;
    for(int i=leftmost;i<=m;i++)
    {
        nmin=min(nmin,a[i][n]);
        nmax=max(nmax,a[i][n]);
    }
    return (nmax-nmin<=lim);
}

bool Process(int lim)
{
    for(int i=1;i<=4;i++)
    {
        if(Check(lim)==true)
            return true;
        Rotate();
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            if(minn>a[i][j])
            {
                minn=a[i][j];
                idi=i;
                idj=j;
            }
        }
    int rs,l=0,r=1e9;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(Process(mid)==true)
        {
            rs=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<rs;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:149:13: warning: 'rs' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<rs;
             ^

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