N4 100 из 100 stress

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int, int>
#define pb(x) push_back(x)
#include <ctime>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}

void cvl(vector <ll> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}


void cvv(vector <vector <int> > &v) {
    for (auto x : v) cv(x);
    cout << "\n";
}

void cvb(vector <bool> v) {
    for (bool x : v) cout << x << ' ';
    cout << "\n";
}

void cvs(vector <string>  v) {
    for (auto a : v) {
        cout << a << "\n";
    }
}

void cvp(vector <pii> a) {
    for (auto p : a) {
        cout << p.first << ' ' << p.second << "\n";
    }
    cout << "\n";
}

ll S(ll a1, ll d, ll n) {
    return (2 * a1 + d * (n - 1) ) * n / 2;
}


ll frx, tox, fry, toy;

bool ok(int i, int j) {
    return i >= frx && i <= tox && j >= fry && j <= toy;
}
vector <int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

bool sh = 0;
ll n, m;
// 10 11
ll dull () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    frx = -2;
    tox = n - 1;
    fry = 0;
    toy = m - 1;
    ll cnt = 1;
    vector <vector <int> > a(n, vector <int> (m, 0));
    /*if (min(n, m) == 1) {
        cout << n * m;
        exit(0);
    }*/
    a[0][0] = 1;
    int i = 0, j = 0, to = 0;
    ll k = 0;
    while (1) {
        //cnt +=
        while ( ok(i + dx[to], j + dy[to]) ) {
            i += dx[to];
            j += dy[to];
            a[i][j] = 1;
            cnt++;
        }
        /*if (sh) {
            cout << "to = " << to << "\n";
            cout << "frx tox = " << frx << ' ' << tox << "\n";
            cout << "fry toy = " << fry << ' ' << toy << "\n";
        }*/
        k++;
        if (to == 0) {
            frx += 2;
            //tox -= 2;
        }
        else if (to == 2) {
            tox -= 2;
        }
        else if (to == 1) {
            fry += 2;
        }
        else if (to == 3) {
            toy -= 2;
        }
        to++;
        to %= 4;
        /*if (sh) {
            cout << "to = " << to << "\n";
            cout << "i + dx[to] j + dy[to] = " << i + dx[to] << ' ' << j + dy[to] << "\n";
        }*/
        if (!ok(i + dx[to], j + dy[to])) {
            break;
        }
    }
    /*if (sh) {
        cout << "i j = " << i << ' ' << j << "\n";
        cout << "to = " << to << "\n";
        cout << "ans\n";
    }*/

    if (sh) {
        cvv(a);
    }
    if (sh) {
        cout << "dull k = " << k << "\n\n\n";
    }
    return cnt;
}

bool ok(ll k) {
    ll resx, resy;
    ll gox = k / 2 + k % 2;
    if (gox == 1) {
        resx = n;
    } else {
        resx = n - (1 + 2 * (gox - 2));
    }

    ll goy = k / 2;
    resy = m - (1 + 2 * (goy - 1));
    if (sh) {
        cout << "check\n";
        cout << "k = " << k << "\n";
        cout << "gox goy = " << gox << ' ' << goy << "\n";
        cout << "resx resy = " << resx << ' ' << resy << "\n";
        cout << "\n";
    }

    if (k % 2 == 0 && resx < 2) {
        return 0;
    }
    if (k % 2 == 1 && resy < 2) {
        return 0;
    }

    bool r = min(resy, resx) >= 0;
    return r;
}

ll get(ll k) {
    ll gox = k / 2 + k % 2;
    ll goy = k / 2;
    ll Sn, Sm;
    Sn = S(n - 1, -2, gox - 1) + n;
    Sm = S(m - 1, -2, goy);
    ll r = Sn + Sm;
    if (sh) {
        cout << "get\n";
        cout << "gox goy = " << gox << ' ' << goy << "\n";
        cout << "Sn Sm = " << Sn << ' ' << Sm << "\n";
        cout << "r = " << r << "\n";
    }

    return r;
}

ll my() {
    if (min(n, m) == 1) {
        return n * m;
    }
    ll L = 0, R = max(n, m) * 2, med;
    while (L + 1 < R) {
        med = (L + R) / 2;
        if (sh) {
            cout << "med = " << med << "\n";
        }
        if (ok(med)) {
            L = med;
        } else {
            R = med;
        }
    }

    if (sh) {
        cout << "L = " << L << "\n";
        cout << "\n\n";
    }

    ll ans = get(L);
    return ans;
}

bool random = 1;
// 10 20
int main() {
    /*cin >> n >> m;
    ll he = dull();
    ll me = my();
    cout << "n m = " << n << ' ' << m << "\n";
    cout << "me he = " << me << ' '<< he << "\n";
    if (me == he) {
        cout << "OK\n";
    }
    else {

        cout << "WA\n";
    }*/
    if (random) {
        srand(time(0));
        bool al = 1;
        int p=0;
        while (p < 1e2) {
            p++;
            n = rand() % 30 + 1;
            m = rand() % 30 + 1;
            ll he = dull();
            ll me = my();
            if (me == he) {
                cout << "OK\n";
                cout << "n m = " << n << ' ' << m << "\n";
            }
            else {
                al = 0;
                cout << "WA\n";
                cout << "n m = " << n << ' ' << m << "\n";
                break;
            }
        }
        cout << "al = " << al << "\n";
    }
    else {
        cin >> n >> m;
        ll he = dull();
        ll me = my();
        if (me == he) {
            cout << "OK\n";
        } else {
            cout << "WA\n";
            cout << "me he = " << me << ' ' << he << "\n";
        }
    }
}