Submission #406681

#	Time	Username	Problem	Language	Result	Execution time	Memory
406681		cpp219	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4085 ms	142224 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
 
#define ll int
#define pb push_back
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=2e3+5;
const ll base=3e18;
const ll mod=1e9+7;
const long double eps=1e-10;
 
 
ll a[maxn][maxn];
ll t[maxn][maxn];
ll pren,prem;
ll b[maxn][maxn];
ll n, m;
vector<pair<ll,pll>> all;
vector<pll> vt;
vector<pll> vt1;
void xoay()
{
    for (int j=m; j>=1; j--)
    {
        for (int i=1; i<=n; i++)
        {
            t[m-j+1][i]=a[i][j];
        }
    }
    for (int i=0; i<vt.size(); i++)
    {
        auto p=vt[i];
        vt[i]=make_pair(m-p.ss+1,p.ff);
    }
    for (int i=0; i<vt1.size(); i++)
    {
        auto p=vt1[i];
        vt1[i]=make_pair(m-p.ss+1,p.ff);
    }
    swap(n,m);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            a[i][j]=t[i][j];
        }
    }
}
ll mx[maxn];
ll mx1[maxn];
bool chk1()
{
    for (int i=1;i<=m;i++) mx[i]=0;
    for (auto to:vt)
    {
        mx[to.ss]=max(mx[to.ss],to.ff);
    }
    mx1[0]=0;
    for (int i=1;i<=m;i++)
    {
       mx1[i]=max(mx1[i-1],mx[i]);
    }
    bool chknw=true;
    for (auto to:vt1)
    {
        if (mx1[to.ss]>=to.ff)
        {
            return false;
            chknw=false;
            break;
        }
    }
    return true;
    /*if (chknw) return true;
    mx1[m+1]=0;
    for (int i=m;i>=1;i--)
    {
        mx1[i]=max(mx1[i+1],mx[i]);
    }
    chknw=true;
     for (auto to:vt1)
    {
        if (mx1[to.ss]>=to.ff)
        {
           return false;
        }
    }
    return true;*/
}
void st()
{
    n=pren;
    m=prem;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++) a[i][j]=b[i][j];
    }
}
bool chk(ll mid)
{
    vt.clear();
    vt1.clear();
    ll p=all[0].ff+mid;
    ll h=all.back().ff-mid;
    for (auto to:all)
    {
        ll cnt=0;
        if (to.ff>p)
            vt.pb(to.ss),cnt++;
        if (to.ff<h)
            vt1.pb(to.ss),cnt++;
 
        if (cnt==2)
        {
            return false;
        }
    }
    if (vt.size()==0||vt1.size()==0)
    {
        return true;
    }
    if (chk1())
    {
        return true;
    }
    xoay();
    if (chk1())
    {
        st();
        return true;
    }
    xoay();
    if (chk1())
    {
        st();
        return true;
    }
    xoay();
    if (chk1())
    {
        st();
        return true;
    }
    st();
 
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
 
    cin>> n>> m;
    pren=n;
    prem=m;
    ll mx=0;
    ll mn=1e9;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin>>a[i][j];
            b[i][j]=a[i][j];
            mx=max(mx,a[i][j]);
            mn=min(mn,a[i][j]);
            all.pb(make_pair(a[i][j],make_pair(i,j)));
        }
    }
    sort(all.begin(),all.end());
    ll l=0, h=mx-mn;
    while (l<=h)
    {
        ll mid=(l+h)/2;
        if (chk(mid)) h=mid-1;
        else l=mid+1;
    }
    
    cout <<l<<endl;
}
 

Compilation message (stderr)

joioi.cpp:11:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   11 | const ll base=3e18;
      |               ^~~~
joioi.cpp: In function 'void xoay()':
joioi.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~
joioi.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0; i<vt1.size(); i++)
      |                   ~^~~~~~~~~~~
joioi.cpp: In function 'bool chk1()':
joioi.cpp:66:10: warning: variable 'chknw' set but not used [-Wunused-but-set-variable]
   66 |     bool chknw=true;
      |          ^~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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