제출 #1188062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188062		maxFedorchuk	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	2115 ms	94852 KiB

joioi

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

const long long MX=2e3+10;

vector < pair < int , pair < int , int > > > ms1;
int a[MX][MX],mtrin[MX][MX],u[MX*MX];
int n,m;

int lstzr;

int clc()
{
    /*
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }
*/
    ms1.clear();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ms1.push_back({a[i][j],{i,j}});
        }
    }
    sort(ms1.begin(),ms1.end());

    for(int i=0;i<n*m;i++)
    {
        mtrin[ms1[i].second.first][ms1[i].second.second]=i;
        u[i]=0;
    }

    lstzr=n*m-1;
    int mn1=n*m-1;
    int rt=ms1.back().first-ms1[0].first;

    while(lstzr)
    {
        int i=ms1[lstzr].second.first;
        while(i>0 && !u[mtrin[i][ms1[lstzr].second.second]])
        {
            int j=ms1[lstzr].second.second;

            while(j>0 && !u[mtrin[i][j]])
            {
                u[mtrin[i][j]]=1;
                mn1=min(mn1,mtrin[i][j]);
                j--;
            }

            i--;
        }

        while(u[lstzr] && lstzr>0)
        {
            lstzr--;
        }

        if(ms1[mn1].first==ms1[0].first)
        {
            break;
        }

        rt=min(rt,max(ms1.back().first-ms1[mn1].first,ms1[lstzr].first-ms1[0].first));
    }

    return rt;
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }

    int ans=clc();

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m/2;j++)
        {
            swap(a[i][j],a[i][m-j+1]);
        }
    }

    ans=min(ans,clc());

    for(int i=1;i<=n/2;i++)
    {
        for(int j=1;j<=m;j++)
        {
            swap(a[n-i+1][j],a[i][j]);
        }
    }

    ans=min(ans,clc());

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m/2;j++)
        {
            swap(a[i][j],a[i][m-j+1]);
        }
    }

    ans=min(ans,clc());

    cout<<ans<<"\n";
    return 0;
}

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