제출 #1157700

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

joioi

#include<bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define F first 
#define S second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T>
using vvector = vector<vector<T>>;
const int INF = 0x3f3f3f3f;

bool ok(int h,int w,vvector<ll> &a,int mn,int mx,ll x) {
    vector<pll> rg1(h+1,{INF,0}),rg2(h+1,{INF,0});
    int d=-1;
    for (int i=1;i<=h;i++) {
        for (ll j=1;j<=w;j++) {
            if (a[i][j]>mn+x) {
                rg2[i].F=min(j,rg2[i].F);
                rg2[i].S=max(j,rg2[i].S);
            }
            if (a[i][j]<mx-x) {
                rg1[i].F=min(j,rg1[i].F);
                rg1[i].S=max(j,rg1[i].S);
            }
        }
        if (!(rg1[i].S<rg2[i].F or rg2[i].S<rg1[i].F)) return false;
        if (d==-1) d=rg1[i].S<rg2[i].F;
        else {
            if (d!=rg1[i].S<rg2[i].F) return false;
        }
    }
    // cout<<x<<" x\n";
    // for (int i=1;i<=h;i++) {
    //     cout<<rg1[i].F<<" "<<rg1[i].S<<"\n";
    // }
    // cout<<"\n";
    // for (int i=1;i<=h;i++) {
    //     cout<<rg2[i].F<<" "<<rg2[i].S<<"\n";
    // }
    // cout<<"--------------\n";
    bool flagd=true;
    ll now=w;
    for (int i=1;i<=h;i++) {
        // cout<<now<<" now\n";
        if (d) {
            now=min(now,rg2[i].F-1);
            if (now<rg1[i].S) {
                flagd=false;
                break;
            }
        } else {
            now=min(now,rg1[i].F-1);
            if (now<rg2[i].S) {
                flagd=false;
                break;
            }
        }
    }
    // cout<<flagd<<" fd\n";
    bool flaga=true;
    now=0;
    for (int i=1;i<=h;i++) {
        // cout<<now<<" now\n";
        if (d) {
            now=max(now,rg1[i].S);
            if (rg2[i].F<=now) {
                flaga=false;
                break;
            }
        } else {
            now=max(now,rg2[i].S);
            if (rg1[i].F<=now) {
                flaga=false;
                break;
            }
        }
    }
    // cout<<flaga<<" fa\n";
    return flaga or flagd;
}

int main() {
    speed;
    ll h,w;
    cin>>h>>w;
    vvector<ll> a(h+1,vector<ll>(w+1));
    ll mn=INF,mx=0;
    for (int i=1;i<=h;i++) {
        for (int j=1;j<=w;j++) {
            cin>>a[i][j];
            mx=max(mx,a[i][j]);
            mn=min(mn,a[i][j]);
        }
    }
    ll l=0,r=INF;
    while (l<r) {
        int mid=l+r>>1;
        if (ok(h,w,a,mn,mx,mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<"\n";
    return 0;
}

/*
4 4
1 1 5 5
1 1 5 5
1 5 5 5
1 1 5 5
*/

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