比赛 20140423 评测结果 AAAAAAAAAA
题目名称 螺旋方阵 最终得分 100
用户昵称 cstdio 运行时间 0.010 s
代码语言 C++ 内存使用 0.94 MiB
提交时间 2014-04-23 08:52:43
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=32769;
const int N=32768;
int sum[SIZEN]={0};
int su[SIZEN]={0},sd[SIZEN]={0},sl[SIZEN]={0},sr[SIZEN]={0};
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
//0123右下左上
int find(int x,int left,int right){//最后一个小于等于x的sum[i]的下标i
	if(left==right) return left;
	int mid=(left+right)/2;
	if(sum[mid+1]>x) return find(x,left,mid);
	else return find(x,mid+1,right);
}
int work(int n,int m){
	int x=find(m-1,0,n);
	int u=su[x],d=sd[x],l=sl[x],r=sr[x];
	int nxt,rem=m-1-sum[x];
	if(x==n) nxt=n;
	else nxt=x+1;
	int temp=min(nxt,rem);
	//下面走下一个长度的"前面那一步"
	if(x&1) l+=temp;//这一步向左
	else r+=temp;//这一步向右
	//下面试图走下一个长度的"后面那一步"
	if(rem>temp){
		rem-=temp;
		if(x&1) u+=rem;
		else d+=rem;
	}
	int i,j;
	i=j=(n+1)/2;//1在最中间
	i+=d,i-=u;
	j+=r,j-=l;
	printf("%d %d\n",i,j);
}
void init(void){
	int dir=0;
	for(int i=1;i<=N;i++){
		sum[i]=sum[i-1]+2*i;
		su[i]=su[i-1],sd[i]=sd[i-1],sl[i]=sl[i-1],sr[i]=sr[i-1];
		if(i&1)	sr[i]+=i,sd[i]+=i;
		else sl[i]+=i,su[i]+=i;
	}
}
int main(){
	freopen("spiral.in","r",stdin);
	freopen("spiral.out","w",stdout);
	init();
	int T;
	scanf("%d",&T);
	while(T--){
		int a,b;
		scanf("%d%d",&a,&b);
		work(a,b);
	}
	return 0;
}