#include "locmin.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<vector<ll>> valarr;

ll get(ll i, ll j)
{
    if(valarr[i][j] != -1) return valarr[i][j];
    return valarr[i][j] = value(i+1, j+1);
}

std::pair <int, int> find_locmin_point(int height, int width)
{
    valarr.assign(height, vector<ll>(width, -1));
    ll lh = 0, rh = height-1, lw = 0, rw = width-1, mid, l, r;
    ll small, smalli;
    while(rh > lh || rw > lw)
    {
        if(lh < rh)
        {
            mid = (lh + rh) / 2;
            small = LLONG_MAX;
            for(ll i = lw; i <= rw; i++)
            {
                ll val = get(mid, i);
                if(val < small)
                {
                    small = val;
                    smalli = i;
                }
            }
            l = mid > 0 ? get(mid-1, smalli) : LLONG_MAX; // up
            r = mid < width-1 ? get(mid+1, smalli) : LLONG_MAX; // down
            if(small < l && small < r) return {mid+1, smalli+1};
            if(l < r)
            {
                rh = mid-1;
            }
            else
            {
                lh = mid+1;
            }
        }
        if(lw < rw)
        {
            mid = (lw + rw) / 2;
            small = LLONG_MAX;
            for(ll i = lh; i <= rh; i++)
            {
                ll val = get(i, mid);
                if(val < small)
                {
                    small = val;
                    smalli = i;
                }
            }
            l = mid > 0 ? get(smalli, mid-1) : LLONG_MAX; // left
            r = mid < width-1 ? get(smalli, mid+1) : LLONG_MAX; // right
            if(small < l && small < r) return {smalli+1, mid+1};
            if(l < r)
            {
                rw = mid-1;
            }
            else
            {
                lh = mid+1;
            }
        }
    }
    return {lh+1, lw+1};
}
