Submission #761999

#	Time	Username	Problem	Language	Result	Execution time	Memory
761999		aaron_dcoder	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	1 ms	212 KiB

joioi

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

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

bool has_assignment(int);

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]);
        }
    }

    sort(A_vals.begin(),A_vals.end());
    min_altitide = A_vals[0];
    max_altitide = *A_vals.crbegin();

    int min_index_known_to_work = A_vals.size();
    int max_index_known_not_to_work = 0;

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

        if (has_assignment(A_vals[mid])) {
            min_index_known_to_work=mid;
        }
        else {
            max_index_known_not_to_work=mid;
        }
    }

    cout << A_vals[min_index_known_to_work];
    
}

//JOI has max
//IOI has min

vector<vector<int>> validity_flags;

bool has_assignment(int max_diff_to_allow) {
    validity_flags = vector(H, vector<int>(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


    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;
            }
        }
    }

    //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;
                }
            }
            else {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto top_right;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    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;
                }
            }
            else {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto bottom_left;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    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;
                }
            }
            else {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    goto bottom_right;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    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;
                }
            }
            else {
                if ((validity_flags[y][x]&CAN_BE_IOI)==0) {
                    return false;
                }
            }
        }
        max_allowed_num_prefix = num_prefix_joi;
    }
    return true;
    

}

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