#include "locmin.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <chrono>

typedef long long llong;
const long long int MAXN = 512;

long long int n, m;
long long int t[MAXN][MAXN];
long long int query(long long int r, long long int c)
{
    if (t[r][c])
    {
        return t[r][c];
    } else
    {
        return t[r][c] = value(r, c);
    }
}

std::pair <long long int,long long int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool inside(long long int row, long long int col)
{
    return row >= 1 && row <= n && col >= 1 && col <= m;
}

std::pair <int, int> find_locmin_point (int N, int M)
{
    n = N;
    m = M;
    long long int BUCKET_SIZE = (n == 1 ? 10 : 800);
    long long int row = -1, col = -1, value = 1e18;
    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    for (long long int i = 0 ; i < BUCKET_SIZE ; ++i)
    {
        long long int r = rng() % n + 1;
        long long int c = rng() % m + 1;
        if (query(r, c) < value)
        {
            row = r;
            col = c;
            value = query(r, c);
        }
    }

    while (true)
    {
        bool foundSmaller = false;
        std::vector <std::pair <int, int> > possible;
        for (const auto &[dr, dc] : delta)
        {
            if (inside(row + dr, col + dc) && query(row + dr, col + dc) < value)
            {
                possible.push_back({row + dr, col + dc});
                foundSmaller = true;

            }
        }
        //random_shuffle(possible.begin(), possible.end());

        if (!foundSmaller)
        {
            return {row, col};
        }
        row = possible.front().first; col = possible.front().second;
        value = query(row, col);
    }
}
