oj.uz

Submission #762015

# Submission time Handle Problem Language Result Execution time Memory
762015 2023-06-20T14:42:09 Z aaron_dcoder The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 2368 ms 227252 KB 
//#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 9 ms 2120 KB Output is correct
17 Correct 16 ms 2500 KB Output is correct
18 Correct 16 ms 2472 KB Output is correct
19 Correct 17 ms 2448 KB Output is correct
20 Correct 16 ms 2228 KB Output is correct
21 Correct 21 ms 2540 KB Output is correct
22 Correct 20 ms 2648 KB Output is correct
23 Correct 19 ms 2536 KB Output is correct
24 Correct 15 ms 2332 KB Output is correct
25 Correct 21 ms 2604 KB Output is correct
26 Correct 19 ms 2620 KB Output is correct
27 Correct 19 ms 2556 KB Output is correct
28 Correct 19 ms 2580 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 9 ms 2120 KB Output is correct
17 Correct 16 ms 2500 KB Output is correct
18 Correct 16 ms 2472 KB Output is correct
19 Correct 17 ms 2448 KB Output is correct
20 Correct 16 ms 2228 KB Output is correct
21 Correct 21 ms 2540 KB Output is correct
22 Correct 20 ms 2648 KB Output is correct
23 Correct 19 ms 2536 KB Output is correct
24 Correct 15 ms 2332 KB Output is correct
25 Correct 21 ms 2604 KB Output is correct
26 Correct 19 ms 2620 KB Output is correct
27 Correct 19 ms 2556 KB Output is correct
28 Correct 19 ms 2580 KB Output is correct
29 Correct 1687 ms 201196 KB Output is correct
30 Correct 1745 ms 196272 KB Output is correct
31 Correct 2048 ms 211236 KB Output is correct
32 Correct 2035 ms 211632 KB Output is correct
33 Correct 1341 ms 184492 KB Output is correct
34 Correct 1913 ms 211624 KB Output is correct
35 Correct 2192 ms 227220 KB Output is correct
36 Correct 1701 ms 198248 KB Output is correct
37 Correct 2368 ms 227252 KB Output is correct