比赛 |
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;
}