Pallo

#include <iostream>
#include <vector>
#include<algorithm>
#include <map>
using namespace std;
using ll = long long;
vector<pair<ll,ll>> reitti;
map<pair<ll,ll>, ll> ma;

int main() {
  ll t;
  cin >> t;
  for (int h = 0; h < t; ++h) {
    ll n, m, k;
    ll p = 0;
    ll mutkat = 0;
    cin >> n >> m >> k;
    ll suunta = 0;
    pair<ll,ll> me = {1,1};
    while (p <= k) {
      //cout << me.first << " " << me.second << endl;
      reitti.push_back(me);
      mutkat++;
      if (suunta == 1) {
        ll ab = m - me.second;
        if (ab == 0) {
          break;
        }
        p += ab;
        ma[me] += p;
        me = {me.first - ab, me.second + ab};
      }
      else if (suunta == 3) {
        ll ab = me.second - 1;
        if (ab == 0) break;
        p += ab;
        ma[me] += p;
        me = {me.first + ab, me.second - ab};
      }
      else if (suunta == 2) {
        ll ab = me.first - 1;
        if (ab == 0) break;
        p += ab;
        ma[me] += p;
        me = {me.first - ab, me.second - ab};
      }
      else if (suunta == 0) {
        ll ab = n - me.first;
        if (ab == 0) break;
        p += ab;
        ma[me] += p;
        me = {me.first + ab, me.second + ab};
      }
      suunta ++;
      suunta = suunta%4;
      //cout << ma[reitti.back()] << " l " << mutkat << endl;
    }
    ll vastaus = 0;
    //cout << me.first << " loppu " << me.second << endl;
    if (k < p || (!(me.first == 1 && me.second == m) && !(me.first == n && me.second == 1) && !(me.first == n && me.second == m))) {
      //cout << "lol" << endl;
      vastaus = mutkat - 1;
    }
    else {
      //cout << k << " " << p << " " << k / p << " " << mutkat << " " << (k / p) * mutkat << endl;
      if (k % p == 0) vastaus = (k / p) * mutkat - 1;
      else {
        ll ka = k % p;
        vastaus = (k / p) * mutkat - 1;
        if (k / p % 2 == 0) {
          int x = -1;
          for (int b = reitti.size()-1; b >= 1; b/=2) {
            while (ka < ma[reitti[x+b]]) x += b;
          }
          vastaus += x+1;
        }
      }
    }
    cout << vastaus << endl;
  }
  for (auto x : ma) {
    ma[x.first] = 0;
  }
  for (int i = reitti.size() - 1; i >= 0; i--) reitti.pop_back();
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED