蒟蒻刚学分治,0pts 求调
查看原帖
蒟蒻刚学分治,0pts 求调
1657369
__liujy楼主2025/7/20 13:11
#include<bits/stdc++.h>
#define int long long
const int N=15,M=10005;
int n,x,y,tot,g[M][M],ans[M][M];
struct node
{
	int x,y,pos,xx,yy;
	inline friend bool operator<(node x,node y)
	{
		if(x.xx!=y.xx) return x.xx<y.xx;
		else return x.yy<y.yy;
	}
}a[M*M];
inline void dfs(int xx,int yy,int x,int y,int len)
{
	if(len==1) return;
	int nx=xx+len-1,ny=yy+len-1,mx=(nx+xx)/2,my=(ny+yy)/2;
	if(x<=mx&&y<=my)
	{
		a[++tot]={mx+1,my+1,1,mx,my+1};
		dfs(xx,yy,x,y,len/2);
		dfs(mx+1,yy,mx+1,my,len/2);
		dfs(mx+1,my+1,mx+1,my+1,len/2);
		dfs(xx,my+1,mx,my+1,len/2);
	}
	else if(x<=mx&&y>my)
	{
		a[++tot]={mx+1,my,2,mx,my};
		dfs(xx,yy,mx,my,len/2);
		dfs(xx,my+1,x,y,len/2);
		dfs(mx+1,yy,mx+1,my,len/2);
		dfs(mx+1,my+1,mx+1,my+1,len/2);
	}
	else if(x>mx&&y<=my)
	{
		a[++tot]={mx,my+1,3,mx,my};
		dfs(mx+1,yy,x,y,len/2);
		dfs(mx+1,my+1,mx+1,my+1,len/2);
		dfs(xx,my+1,mx,my+1,len/2);
		dfs(xx,yy,mx,my,len/2);
	}
	else if(x>mx&&y>my)
	{
		a[++tot]={mx,my,4,mx,my};
		dfs(xx,yy,mx,my,len/2);
		dfs(xx,my+1,mx,my+1,len/2);
		dfs(mx+1,my+1,x,y,len/2);
		dfs(mx+1,yy,mx+1,my,len/2);
	}
}
signed main()
{
	scanf("%lld%lld%lld",&n,&x,&y);
	int len=(1<<n);
	dfs(1,1,x,y,len);
	std::sort(a+1,a+tot+1);
	int cnt=0;
	for(int i=1;i<=tot;i++)
	{
		if(a[i].pos==1) ans[a[i].x][a[i].y]=ans[a[i].x-1][a[i].y]=ans[a[i].x][a[i].y-1]=++cnt;
		else if(a[i].pos==2) ans[a[i].x][a[i].y]=ans[a[i].x-1][a[i].y]=ans[a[i].x][a[i].y+1]=++cnt;
		else if(a[i].pos==3) ans[a[i].x][a[i].y]=ans[a[i].x][a[i].y-1]=ans[a[i].x+1][a[i].y]=++cnt;
		else ans[a[i].x][a[i].y]=ans[a[i].x+1][a[i].y]=ans[a[i].x][a[i].y+1]=++cnt;
	}
	for(int i=1;i<=len;i++)
		for(int j=1;j<=len;j++)
			printf("%lld %c",ans[i][j],(j==len?'\n':' '));
	return 0;
}
2025/7/20 13:11
加载中...