Submission #25494

---

Source Code Expand

#include<queue>
#include<cstdio>
#include"maze.h"
#include"grader.h"

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct point{
	int x,y;
	point(){}
	point(int x,int y):x(x),y(y){}
};

void find_pos(int W,int H,int &x0,int &y0){
	int k;
	for(k=0;k<4;k++) if(query(dx[k],dy[k])==0) break;

	int left=0;
	{
		int lo=0,hi=W/2;
		while(lo<hi){
			int mi=(lo+hi+1)/2;
			if(query(-2*mi,0)==0) lo=mi; else hi=mi-1;
		}
		left=min(left,-2*lo);
	}
	if(k<4){
		int lo=0,hi=W/2;
		while(lo<hi){
			int mi=(lo+hi+1)/2;
			if(query(-2*mi+dx[k],dy[k])==0) lo=mi; else hi=mi-1;
		}
		left=min(left,-2*lo+dx[k]);
	}

	int top=0;
	{
		int lo=0,hi=H/2;
		while(lo<hi){
			int mi=(lo+hi+1)/2;
			if(query(0,-2*mi)==0) lo=mi; else hi=mi-1;
		}
		top=min(top,-2*lo);
	}
	if(k<4){
		int lo=0,hi=H/2;
		while(lo<hi){
			int mi=(lo+hi+1)/2;
			if(query(dx[k],-2*mi+dy[k])==0) lo=mi; else hi=mi-1;
		}
		top=min(top,-2*lo+dy[k]);
	}

	x0=1-left;
	y0=1-top;
}

void taro(int W,int H,int M[1000][1000]){
	int tx,ty;
	find_pos(W,H,tx,ty);

	rep(y,H) rep(x,W) if(x%2^y%2) send(M[y][x]);
	rep(i,10) send(!!(tx&1<<i));
	rep(i,10) send(!!(ty&1<<i));
}

int jiro(int W,int H,int n_sig,int sig[]){
	int i_sig=0;
	static int M[1000][1000];
	rep(y,H) rep(x,W) {
		if(x%2^y%2) M[y][x]=sig[i_sig++];
		else        M[y][x]=(x%2&&y%2?0:1);
	}

	int tx=0,ty=0; // taro のいる座標
	rep(i,10) tx|=sig[i_sig++]<<i;
	rep(i,10) ty|=sig[i_sig++]<<i;

	int jx,jy; // jiro のいる座標
	find_pos(W,H,jx,jy);

	// BFS
	static int d[1000][1000];
	rep(y,H) rep(x,W) d[y][x]=INF;
	d[jy][jx]=0;

	queue<point> Q;
	Q.push(point(jx,jy));
	while(!Q.empty()){
		int x=Q.front().x,y=Q.front().y; Q.pop();
		rep(k,4){
			int xx=x+dx[k],yy=y+dy[k];
			if(M[yy][xx]==0 && d[yy][xx]==INF){
				d[yy][xx]=d[y][x]+1;
				Q.push(point(xx,yy));
			}
		}
	}

	return d[ty][tx];
}

Submission Info

Judge Result