Philosopher's walk gym divide and conquer + fractal

Topic link

Knowing the relationship between a structure and its substructure , Can “ Quarter search ” That coordinates .（ I think this process is very similar to binary search ）

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

int n,m;
int ans_x, ans_y;

int nxt_dir(int dir, int nxt, int p)
{
    
	if (dir==1)
	{
    
		if (nxt==1) return 2;
		else if (nxt==2) {
    ans_y+=p; return 1;}
		else if (nxt==3) {
    ans_x+=p; ans_y+=p; return 1;}
		else if (nxt==4) {
    ans_x+=p; return 3;}
	}
	else if (dir==2)
	{
    
		if (nxt==1) return 1;
		else if (nxt==2) {
    ans_x+=p; return 2;}
		else if (nxt==3) {
    ans_x+=p; ans_y+=p; return 2;}
		else {
    ans_y+=p;return 4;}
	}
	else if (dir==3)
	{
    
		if (nxt==1) {
    ans_x+=p;ans_y+=p; return 4;}
		else if (nxt==2) {
    ans_y+=p; return 3;}
		else if (nxt==3) return 3;
		else {
    ans_x+=p; return 1;}
	}
	else
	{
    
		if (nxt==1) {
    ans_x+=p; ans_y+=p; return 3;}
		else if (nxt==2) {
    ans_x+=p; return 4;}
		else if (nxt==3) return 4;
		else {
    ans_y+=p; return 2;}
	}
}

void dfs(int len, int tot, int cur, int dir)
{
    
	int tmp=tot/4;
	if (cur<=tmp)
	{
    
		int n_dir=nxt_dir(dir,1,len/2);
		if (tmp==1) return;
		dfs(len/2,tmp,cur,n_dir);	
	}
	else if (cur<=2*tmp)
	{
    
		int n_dir=nxt_dir(dir,2,len/2);
		if (tmp==1) return;
		dfs(len/2,tmp,cur-tmp,n_dir);
	}
	else if (cur<=3*tmp)
	{
    
		int n_dir=nxt_dir(dir,3,len/2);
		if (tmp==1) return;
		dfs(len/2,tmp,cur-2*tmp,n_dir);
	}
	else
	{
    
		int n_dir=nxt_dir(dir,4,len/2);
		if (tmp==1) return;
		dfs(len/2,tmp,cur-3*tmp,n_dir);
	}
}

int main()
{
    
   	FAST; 
	while(cin>>n>>m)
	{
    
		ans_x=ans_y=0;
		int now=n*n;
		dfs(n,now,m,1);
		++ans_x, ++ans_y;
		cout<<ans_x<<' '<<ans_y<<endl;
	}
return 0;
}

There's a simpler way , Divide and conquer + Coordinate transformation
Just draw a picture of the coordinate transformation .

#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn = 1e5+5;

using namespace std;

int n,m;
struct node
{
    
	int x,y;
	node (int xx, int yy){
    
		x=xx, y=yy;
	}	
};

node work(int n_n, int m_m)
{
    
	if (n_n==1) return node(0,0);
	
	int tmp=n_n*n_n/4;
	int pos=(m_m-1)/tmp;  //m_m Need to get 1 
	
	int nxt=m_m%tmp;
	if (nxt==0) nxt=tmp;  // Special judgement m_m%tmp The situation of  
	
	node res=work(n_n/2,nxt);
	
	if (pos==0) return node(res.y,res.x);
	else if (pos==1) return node(res.x,res.y+n_n/2);
	else if (pos==2) return node(res.x+n_n/2,res.y+n_n/2);
	else if (pos==3) return node(n_n-res.y-1,n_n/2-res.x-1);
}

int main()
{
    
   	FAST; 
	while(cin>>n>>m)
	{
    
		node ans(0,0);
		ans=work(n,m);
		cout<<ans.x+1<<' '<<ans.y+1<<endl;
	}
return 0;
}