gym-101667F Philosopher's Walk

Philosopher's Walk

递归分治

判断一下当前走的位置是属于 \(4\) 个块中的第几个块，然后递归计算一下在边长变小一倍后，他应该所处的位置，然后再对原位置进行旋转或平移的操作

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pii pair<int, int>

pii solve(ll n, ll m)
{
    if(n == 2)
    {
        if(m == 1) return {1, 1};
        if(m == 2) return {1, 2};
        if(m == 3) return {2, 2};
        return {2, 1};
    }
    ll temp = n * n / 4;
    pii ans = {0, 0};
    if(m <= temp)
    {
        ans = solve(n / 2, m);
        swap(ans.first, ans.second);
    }
    else if(m <= temp * 2)
    {
        ans = solve(n / 2, m - temp);
        ans.second += n / 2;
    }
    else if(m <= temp * 3)
    {
        ans = solve(n / 2, m - temp * 2);
        ans.first += n / 2;
        ans.second += n / 2;
    }
    else
    {
        ans = solve(n / 2, m - temp * 3);
        ans.first = n / 2 - ans.first + 1;
        ans.second = n / 2 - ans.second + 1;
        swap(ans.first, ans.second);
        ans.first += n / 2;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, m;
    cin >> n >> m;
    auto [x, y] = solve(n, m);
    cout << x << " " << y << endl;
    return 0;
}