Submission #25283


Source Code Expand

#include<queue>
#include<cstdio>
#include<algorithm>
#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 taro(int W,int H,int M[1000][1000]){
	int tx=INF,ty=INF;
	for(int y=-1000;y<=1000;y++) for(int x=-1000;x<=1000;x++) {
		if(query(x,y)==0){
			tx=min(tx,x);
			ty=min(ty,y);
		}
	}
	tx=1-tx; ty=1-ty;

	rep(y,H) rep(x,W) 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[]){
	static int M[1000][1000];
	rep(y,H) rep(x,W) M[y][x]=sig[y*W+x];

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

	int jx=INF,jy=INF;
	for(int y=-1000;y<=1000;y++) for(int x=-1000;x<=1000;x++) {
		if(query(x,y)==0){
			jx=min(jx,x);
			jy=min(jy,y);
		}
	}
	jx=1-jx; jy=1-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

Submission Time
Task B - にひきのきつね と くらがりのめいろ (Two Foxes and the Dark Maze)
User fura2
Language IOI-Style C++ (GCC 5.4.1)
Score 13
Code Size 1391 Byte
Status AC
Exec Time 780 ms
Memory 25472 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4 Subtask5
Score / Max Score 13 / 13 0 / 11 0 / 21 0 / 21 0 / 34
Status
AC × 56
AC × 56
AC × 56
AC × 56
AC × 56
Set Name Test Cases
Subtask1 subtask/1, subtask/10, subtask/11, subtask/12, subtask/13, subtask/14, subtask/15, subtask/16, subtask/17, subtask/18, subtask/19, subtask/2, subtask/20, subtask/21, subtask/22, subtask/23, subtask/24, subtask/25, subtask/26, subtask/27, subtask/28, subtask/29, subtask/3, subtask/30, subtask/31, subtask/32, subtask/33, subtask/34, subtask/35, subtask/36, subtask/37, subtask/38, subtask/39, subtask/4, subtask/40, subtask/41, subtask/42, subtask/43, subtask/44, subtask/45, subtask/46, subtask/47, subtask/48, subtask/49, subtask/5, subtask/50, subtask/51, subtask/52, subtask/53, subtask/54, subtask/55, subtask/56, subtask/6, subtask/7, subtask/8, subtask/9
Subtask2 subtask/1, subtask/10, subtask/11, subtask/12, subtask/13, subtask/14, subtask/15, subtask/16, subtask/17, subtask/18, subtask/19, subtask/2, subtask/20, subtask/21, subtask/22, subtask/23, subtask/24, subtask/25, subtask/26, subtask/27, subtask/28, subtask/29, subtask/3, subtask/30, subtask/31, subtask/32, subtask/33, subtask/34, subtask/35, subtask/36, subtask/37, subtask/38, subtask/39, subtask/4, subtask/40, subtask/41, subtask/42, subtask/43, subtask/44, subtask/45, subtask/46, subtask/47, subtask/48, subtask/49, subtask/5, subtask/50, subtask/51, subtask/52, subtask/53, subtask/54, subtask/55, subtask/56, subtask/6, subtask/7, subtask/8, subtask/9
Subtask3 subtask/1, subtask/10, subtask/11, subtask/12, subtask/13, subtask/14, subtask/15, subtask/16, subtask/17, subtask/18, subtask/19, subtask/2, subtask/20, subtask/21, subtask/22, subtask/23, subtask/24, subtask/25, subtask/26, subtask/27, subtask/28, subtask/29, subtask/3, subtask/30, subtask/31, subtask/32, subtask/33, subtask/34, subtask/35, subtask/36, subtask/37, subtask/38, subtask/39, subtask/4, subtask/40, subtask/41, subtask/42, subtask/43, subtask/44, subtask/45, subtask/46, subtask/47, subtask/48, subtask/49, subtask/5, subtask/50, subtask/51, subtask/52, subtask/53, subtask/54, subtask/55, subtask/56, subtask/6, subtask/7, subtask/8, subtask/9
Subtask4 subtask/1, subtask/10, subtask/11, subtask/12, subtask/13, subtask/14, subtask/15, subtask/16, subtask/17, subtask/18, subtask/19, subtask/2, subtask/20, subtask/21, subtask/22, subtask/23, subtask/24, subtask/25, subtask/26, subtask/27, subtask/28, subtask/29, subtask/3, subtask/30, subtask/31, subtask/32, subtask/33, subtask/34, subtask/35, subtask/36, subtask/37, subtask/38, subtask/39, subtask/4, subtask/40, subtask/41, subtask/42, subtask/43, subtask/44, subtask/45, subtask/46, subtask/47, subtask/48, subtask/49, subtask/5, subtask/50, subtask/51, subtask/52, subtask/53, subtask/54, subtask/55, subtask/56, subtask/6, subtask/7, subtask/8, subtask/9
Subtask5 subtask/1, subtask/10, subtask/11, subtask/12, subtask/13, subtask/14, subtask/15, subtask/16, subtask/17, subtask/18, subtask/19, subtask/2, subtask/20, subtask/21, subtask/22, subtask/23, subtask/24, subtask/25, subtask/26, subtask/27, subtask/28, subtask/29, subtask/3, subtask/30, subtask/31, subtask/32, subtask/33, subtask/34, subtask/35, subtask/36, subtask/37, subtask/38, subtask/39, subtask/4, subtask/40, subtask/41, subtask/42, subtask/43, subtask/44, subtask/45, subtask/46, subtask/47, subtask/48, subtask/49, subtask/5, subtask/50, subtask/51, subtask/52, subtask/53, subtask/54, subtask/55, subtask/56, subtask/6, subtask/7, subtask/8, subtask/9
Case Name Status Exec Time Memory
subtask/1 AC 566 ms 25472 KB
subtask/10 AC 568 ms 25388 KB
subtask/11 AC 543 ms 25392 KB
subtask/12 AC 780 ms 25384 KB
subtask/13 AC 568 ms 25384 KB
subtask/14 AC 579 ms 25376 KB
subtask/15 AC 573 ms 25376 KB
subtask/16 AC 598 ms 25412 KB
subtask/17 AC 564 ms 25376 KB
subtask/18 AC 577 ms 25380 KB
subtask/19 AC 564 ms 25380 KB
subtask/2 AC 577 ms 25404 KB
subtask/20 AC 586 ms 25428 KB
subtask/21 AC 131 ms 17708 KB
subtask/22 AC 95 ms 8664 KB
subtask/23 AC 135 ms 17580 KB
subtask/24 AC 101 ms 8776 KB
subtask/25 AC 591 ms 25384 KB
subtask/26 AC 120 ms 9832 KB
subtask/27 AC 433 ms 22176 KB
subtask/28 AC 523 ms 24488 KB
subtask/29 AC 419 ms 17392 KB
subtask/3 AC 576 ms 25388 KB
subtask/30 AC 314 ms 16988 KB
subtask/31 AC 329 ms 16856 KB
subtask/32 AC 139 ms 17828 KB
subtask/33 AC 142 ms 17820 KB
subtask/34 AC 110 ms 9076 KB
subtask/35 AC 111 ms 9080 KB
subtask/36 AC 109 ms 9072 KB
subtask/37 AC 112 ms 9064 KB
subtask/38 AC 91 ms 8740 KB
subtask/39 AC 93 ms 8712 KB
subtask/4 AC 587 ms 25400 KB
subtask/40 AC 90 ms 8740 KB
subtask/41 AC 91 ms 8704 KB
subtask/42 AC 551 ms 25376 KB
subtask/43 AC 571 ms 25300 KB
subtask/44 AC 570 ms 25384 KB
subtask/45 AC 578 ms 25384 KB
subtask/46 AC 570 ms 25380 KB
subtask/47 AC 589 ms 25380 KB
subtask/48 AC 604 ms 25388 KB
subtask/49 AC 600 ms 25404 KB
subtask/5 AC 562 ms 25376 KB
subtask/50 AC 597 ms 25380 KB
subtask/51 AC 593 ms 25388 KB
subtask/52 AC 549 ms 25380 KB
subtask/53 AC 567 ms 25376 KB
subtask/54 AC 598 ms 25384 KB
subtask/55 AC 576 ms 25392 KB
subtask/56 AC 580 ms 25384 KB
subtask/6 AC 594 ms 25392 KB
subtask/7 AC 543 ms 25388 KB
subtask/8 AC 572 ms 25408 KB
subtask/9 AC 542 ms 25416 KB