//#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
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;
}
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])) {
min_index_known_to_work=mid;
}
else {
max_index_known_not_to_work=mid;
}
}
cout << answer_candidates[min_index_known_to_work];
}
/*
3 3
500 2 3
900 6 7
2 8 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 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 |
340 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 |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 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 |
340 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 |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
296 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 |
340 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 |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
