제출 #338752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338752		blue	The Kingdom of JOIOI (JOI17_joioi)	C++11	0 / 100	121 ms	47256 KiB

joioi

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

int H, W;
int A[2000*2000];
int mx_pos, mn_pos;
int mx, mn;

queue<int> tbv;
int color[2000*2000]; //0 -> either, 1 -> must be with mn, 2 -> must be with mx
vector<int> visit(2000*2000);
vector<int> edge;

int b_search(int a, int b)
{
    //cout << a << ' ' << b << '\n';
    if(a == b) return a;

    int m = (a+b)/2;
    // cout << "m = " << m << '\n';

    for(int i = 0; i < H*W; i++)
    {
        if(mx - A[i] <= m && A[i] - mn <= m)
        {
            color[i] = 0;
           // cout << 0;
        }
        else if(A[i] - mn <= m)
        {
            color[i] = 1;
           // cout << 1;
        }
        else if(mx - A[i] <= m)
        {
            color[i] = 2;
           // cout << 2;
        }
        else return b_search(m+1, b);
        // if(i % W == W-1) cout << '\n';
    }

    //Checking condition 3
    int count = 0;
    visit = vector<int>(2000*2000, 0);

    int col;

    for(int i = 0; i < H*W; i++)
    {
        if(visit[i]) continue;
        if(!color[i]) continue;

        // cout << "   i = " << i << '\n';
        col = color[i];
        count++;
        if(count > 2) return b_search(m+1, b);
        visit[i] |= color[i];
        while(!tbv.empty()) tbv.pop();
        tbv.push(i);



        while(!tbv.empty())
        {
            int u = tbv.front();
            tbv.pop();
            // cout << "       u = " << u << '\n';

            edge.clear();
            if(u >= W) edge.push_back(u - W);
            if(u < (H-1)*W) edge.push_back(u + W);
            if(u % W > 0) edge.push_back(u - 1);
            if(u % W < W-1) edge.push_back(u + 1);

            for(int v: edge)
            {
                // cout << "           v = " << v << ' ' << color[v] << ' ' << color[u] << '\n';
                if(color[v] != 0 && color[v] != col) continue;
                if(visit[v] & col) continue;
                visit[v] |= col;
                tbv.push(v);
            }
        }
    }

    // cout << m << " checking B\n";

    // for(int i = 0; i < H*W; i++)
    // {
    //     cout << visit[i];
    //     if(i % W == W-1) cout << '\n';
    // }

    //Checking condition 4
    int got1, got2, last;

    for(int i = 0; i < H; i++)
    {
        got1 = got2 = last = 0;
        for(int j = 0; j < W; j++)
        {
            if(color[W*i + j] == 1)
            {
                if(got1 && got2 && (last == 2)) return b_search(m+1, b);
                got1 = 1;
                last = 1;
            }
            else if(color[W*i + j] == 2)
            {
                if(got1 && got2 && (last == 1)) return b_search(m+1, b);
                got2 = 1;
                last = 2;
            }
        }
    }

    for(int j = 0; j < W; j++)
    {
        got1 = got2 = last = 0;
        for(int i = 0; i < H; i++)
        {
            if(color[W*i + j] == 1)
            {
                if(got1 && got2 && (last == 2)) return b_search(m+1, b);
                got1 = 1;
                last = 1;
            }
            else if(color[W*i + j] == 2)
            {
                if(got1 && got2 && (last == 1)) return b_search(m+1, b);
                got2 = 1;
                last = 2;
            }
        }
    }

    return b_search(a, m);
}

int main()
{
    cin >> H >> W;
    for(int i = 0; i < H*W; i++)
        cin >> A[i];

    mx_pos = mn_pos = 0;
    for(int i = 1; i < H*W; i++)
    {
        if(A[i] > A[mx_pos]) mx_pos = i;
        if(A[i] < A[mn_pos]) mn_pos = i;
    }
    mx = A[mx_pos];
    mn = A[mn_pos];

    cout << b_search(0, 1e9) << '\n';
}

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