제출 #762015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762015		aaron_dcoder	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2368 ms	227252 KiB

joioi

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<ll>> A;
vector<ll> A_vals;
ll max_altitide, min_altitide;
ll H, W;



//JOI has max
//IOI has min

vector<vector<ll>> validity_flags;

bool has_assignment(int max_diff_to_allow) {
    validity_flags = vector(H, vector<ll>(W)); 
    // ab where a,b are bits representing which kingdom it can be part of (JOI,IOI:LSB)
#define CAN_BE_JOI 0b10
#define CAN_BE_IOI 0b01

    //cout << "\narr at" << max_diff_to_allow << "\n";
    for (int y = 0; y < H; y++)
    {
        for (int x =0; x < W; x++) {
            if (max_altitide-A[y][x] <= max_diff_to_allow) {
                validity_flags[y][x] |= CAN_BE_JOI;
            }
            if (A[y][x]-min_altitide <= max_diff_to_allow) {
                validity_flags[y][x] |= CAN_BE_IOI;
            }
            if (validity_flags[y][x]==0) {
                return false;
            }

            //cout << validity_flags[y][x];
        }
        //cout << "\n";
    }

    //we will make cases for each pos of joi and ioi in opp corner


    //joi top left
    int max_allowed_num_prefix = W;
    for (int y = 0; y < H; y++)
    {
        int num_prefix_joi = 0;
        bool has_not_switched = true;
        for (int x =0; x < W; x++) {
            if (has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_JOI)==0 || num_prefix_joi==max_allowed_num_prefix) {
                    has_not_switched = false;
                }
                else {
                    num_prefix_joi++;
                    continue;
                }
            }
            if (!has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto top_right;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    //cout << "\ntl\n";
    return true;

    top_right:
    //joi top right
    max_allowed_num_prefix = W;
    for (int y = 0; y < H; y++)
    {
        int num_prefix_joi = 0;
        bool has_not_switched = true;
        for (int x =W-1; x>=0 ; x--) {
            if (has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_JOI)==0 || num_prefix_joi==max_allowed_num_prefix) {
                    has_not_switched = false;
                }
                else {
                    num_prefix_joi++;
                    continue;
                }
            }
            if (!has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto bottom_left;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
        //cout << "\nh:"<< max_allowed_num_prefix << "";
    }
    //cout << "\ntr\n";
    return true;

    bottom_left:
    //joi bottom_left
    max_allowed_num_prefix = W;
    for (int y = H-1; y >= 0; y--)
    {
        int num_prefix_joi = 0;
        bool has_not_switched = true;
        for (int x =0; x < W; x++) {
            if (has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_JOI)==0 || num_prefix_joi==max_allowed_num_prefix) {
                    has_not_switched = false;
                }
                else {
                    num_prefix_joi++;
                    continue;
                }
            }
            if (!has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto bottom_right;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    //cout << "\nbl\n";
    return true;

    bottom_right:
    //joi bottom_right
    max_allowed_num_prefix = W;
    for (int y = H-1; y >= 0; y--)
    {
        int num_prefix_joi = 0;
        bool has_not_switched = true;
        for (int x =W-1; x>=0 ; x--) {
            if (has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_JOI)==0 || num_prefix_joi==max_allowed_num_prefix) {
                    has_not_switched = false;
                }
                else {
                    num_prefix_joi++;
                    continue;
                }
            }
            if (!has_not_switched) {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    return false;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    //cout << "\nbr\n";
    return true;
    

}


int main() {
    
    cin >> H >> W;
    A = vector(H, vector<ll>(W));
    A_vals.reserve(H*W+1);

    for (int y = 0; y < H; y++)
    {
        for (int x =0; x < W; x++) {
            cin >> A[y][x];
            A_vals.push_back(A[y][x]);
        }
    }

    min_altitide = *min_element(A_vals.cbegin(), A_vals.cend());
    max_altitide = *max_element(A_vals.cbegin(), A_vals.cend());

    vector<ll> answer_candidates;
    answer_candidates.reserve(H*W*2+1);
    for (const ll& Ai : A_vals)
    {
        answer_candidates.push_back(Ai-min_altitide);
        answer_candidates.push_back(max_altitide-Ai);
    }
    sort(answer_candidates.begin(), answer_candidates.end());

    ll min_index_known_to_work = answer_candidates.size()-1;
    ll max_index_known_not_to_work = 0;

    while (max_index_known_not_to_work+1<min_index_known_to_work)
    {
        ll mid = (max_index_known_not_to_work+min_index_known_to_work)/2;

        if (has_assignment(answer_candidates[mid])) {
            //cout << "\nyes:" << answer_candidates[mid];
            min_index_known_to_work=mid;
        }
        else {
            //cout << "\nno:" << answer_candidates[mid];

            max_index_known_not_to_work=mid;
        }
    }

    cout << answer_candidates[min_index_known_to_work];
    
}

/*
3 3
500 2 3
900 6 7000
500 8 7
*/

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