제출 #233363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233363		nicolaalexandra	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4074 ms	114284 KiB

joioi

#include <bits/stdc++.h>
#define DIM 2010
#define INF 2000000000
using namespace std;
int a[DIM][DIM],b[DIM][DIM],viz[DIM][DIM];
struct idk{
    int val,l,c;
} v[DIM*DIM];
deque <pair<int,int> > c;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
int n,m,i,j,sol,mini,maxi,k;
int verif (int val){

    /// toate valorile < maxi - val trb puse in zona minimelor
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            viz[i][j] = 0;

    for (int i=1;i<=k;i++){
        if (v[i].val >= maxi - val)
            break;
        int lin = v[i].l, col = v[i].c;
        if (viz[lin][col])
            continue;

        c.clear();
        c.push_back(make_pair(lin,col));
        viz[lin][col] = 1;
        while (!c.empty()){
            int ic = c.front().first;
            int jc = c.front().second;
            c.pop_front();
            for (int dir=0;dir<=3;dir++){
                int iv = ic + di[dir];
                int jv = jc + dj[dir];
                if (iv >= lin && iv <= n && jv >= 1 && jv <= col && !viz[iv][jv]){
                    viz[iv][jv] = 1;
                    c.push_back(make_pair(iv,jv));
                }}}}

    int maxim = 0, maxim2 = 0, minim = INF, minim2 = INF;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            if (viz[i][j]){
                minim = min (minim,a[i][j]);
                maxim = max (maxim,a[i][j]);
            } else {
                minim2 = min (minim2,a[i][j]);
                maxim2 = max (maxim2,a[i][j]);
            }}

    if (max (maxim - minim, maxim2 - minim2) > val)
        return 0;
    return 1;
}

void solve (){

    int st = 0, dr = maxi - mini, val;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif (mid)){
            val = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    sol = min (sol,val);

}

inline int cmp (idk a, idk b){
    return a.val < b.val;
}

void roteste(){

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            b[m-j+1][i] = a[i][j];
    swap (n,m);

    k = 0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            a[i][j] = b[i][j];
            v[++k] = {a[i][j],i,j};
        }
    sort (v+1,v+k+1,cmp);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    mini = INF;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            cin>>a[i][j];
            mini = min (mini,a[i][j]);
            maxi = max (maxi,a[i][j]);
            v[++k] = {a[i][j],i,j};
        }

    sort (v+1,v+k+1,cmp);

    sol = INF;
    solve();

    roteste();
    solve();

    roteste();
    solve();

    roteste();
    solve();

    cout<<sol;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'void solve()':
joioi.cpp:60:35: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int st = 0, dr = maxi - mini, val;
                                   ^~~

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