結果

問題 No.331 CodeRunnerでやれ
ユーザー koyumeishikoyumeishi
提出日時 2015-12-25 01:11:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 345 ms / 5,000 ms
コード長 3,516 bytes
コンパイル時間 1,335 ms
コンパイル使用メモリ 107,832 KB
実行使用メモリ 25,616 KB
平均クエリ数 440.71
最終ジャッジ日時 2024-07-16 22:46:08
合計ジャッジ時間 6,652 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
25,232 KB
testcase_01 AC 156 ms
25,616 KB
testcase_02 AC 187 ms
24,592 KB
testcase_03 AC 214 ms
25,232 KB
testcase_04 AC 180 ms
25,220 KB
testcase_05 AC 173 ms
25,220 KB
testcase_06 AC 217 ms
24,592 KB
testcase_07 AC 207 ms
25,220 KB
testcase_08 AC 229 ms
24,848 KB
testcase_09 AC 305 ms
25,220 KB
testcase_10 AC 267 ms
25,488 KB
testcase_11 AC 236 ms
24,592 KB
testcase_12 AC 256 ms
24,964 KB
testcase_13 AC 273 ms
24,836 KB
testcase_14 AC 312 ms
25,232 KB
testcase_15 AC 289 ms
24,580 KB
testcase_16 AC 345 ms
24,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <stack>
#include <random>
using namespace std;
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T> ostream& operator << (ostream& os, vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"\n":" ");return os;}

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

#include <cassert>

int main(){
	char buff[100];
	int s = 0;

	int cnt = 0;

	// 0 ?
	// 1 visit
	// 2 wall
	// 3 space
	vector<vector<int>> field(50, vector<int>(50, 0));

	int x = 25;
	int y = 25;
	int dir = 0;

	auto update = [&](){
		string s(buff);
		if(s=="Merry Christmas!") return -1;
		if(s=="20151224") return -2;

		int d;
		sscanf(buff, "%d", &d);
		for(int k=1; k<=d; k++){
			if( !field[x + k*dx[dir]][y + k*dy[dir]] ) field[x + k*dx[dir]][y + k*dy[dir]] = 3;
		}
		field[x + (d+1)*dx[dir] ][ y + (d+1) * dy[dir] ] = 2;
		return d;
	};

	auto check_foward = [&](){
		return field[x + dx[dir] ][y + dy[dir]];
	};

	auto check_right = [&](){
		return field[x + dx[(dir+1)&3]][y + dy[(dir+1)&3]];
	};
	auto check_left = [&](){
		return field[x + dx[(dir+1)&3]][y + dy[(dir+1)&3]];
	};

	auto go_foward = [&](){
		if(field[x + dx[dir]][y + dy[dir]] == 2) return;
		puts("F");
		cnt++;
		fflush(stdout);
		x += dx[dir];
		y += dy[dir];
		gets(buff);
		update();
	};

	auto go_backward = [&](){
		if(field[x + dx[(dir+2)&3]][y + dy[(dir+2)&3]] == 2) return;
		puts("B");
		cnt++;
		fflush(stdout);
		x -= dx[dir];
		y -= dy[dir];
		gets(buff);
		update();
	};

	auto turn_right = [&](){
		puts("R");
		cnt++;
		fflush(stdout);
		dir = (dir+1)&3;
		gets(buff);
		update();

	};

	auto turn_left = [&](){
		puts("L");
		cnt++;
		fflush(stdout);
		dir = (dir+3)&3;
		gets(buff);
		update();
	};

	stack<pair<pair<int,int>,int>> st;

	auto move_ = [&](pair<int,int> to){
		int diff_x = abs(to.first - x);
		int diff_y = abs(to.second - y);
		assert(diff_x + diff_y <= 1);

		if(pair<int,int>{x,y} != to){
			if(to == pair<int,int>{x+dx[(dir+1)&3], y+dy[(dir+1)&3]}){
				turn_right();
				go_foward();
			}else if(to == pair<int,int>{x+dx[(dir+3)&3], y+dy[(dir+3)&3]}){
				turn_left();
				go_foward();
			}else if(to == pair<int,int>{x+dx[(dir+2)&3], y+dy[(dir+2)&3]}){
				go_backward();
			}else{
				go_foward();
			}
		}
	};

	gets(buff);
/*
	while(true){
		int d = update();
		if(d<=0) break;
		go_foward();
	}
*/
	stack<pair<int,int>> unko;

	while(true){
		assert(cnt<=5000);

		int d = update();
		if(d==-1) return 0;
		if(d==-2){
			go_foward();
			continue;
		}


		if(field[x][y] == 0 || field[x][y] == 3){

			field[x][y] = 1;

			vector<pair<pair<int,int>,int>> hoge(5, {{-1,-1},-1});
			for(int i=0; i<4; i++){
				int z = check_foward();
				if(z==0 || z==3){
					hoge[i] = {{x,y},dir};
				}
				turn_right();
				update();
			}
			for(int i:{2,3,0,1}){
				if(hoge[i] == hoge[4]) continue;
				st.push(hoge[i]);
			}

		}

		while(st.top().first != pair<int,int>{x,y}){
			move_(unko.top());
			unko.pop();
		}

		if(st.top().first == pair<int,int>{x,y}){

			unko.push({x,y});
			
			while(st.top() != pair<pair<int,int>,int>{{x,y}, dir}){
				turn_right();
			}
			st.pop();
			go_foward();
			continue;
		}

	}
	return 0;
}
0