結果

問題 No.331 CodeRunnerでやれ
コンテスト
ユーザー koyumeishi
提出日時 2015-12-25 00:44:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,826 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,133 ms
コンパイル使用メモリ 112,680 KB
実行使用メモリ 79,420 KB
平均クエリ数 0.06
最終ジャッジ日時 2024-07-16 22:44:36
合計ジャッジ時間 8,380 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other AC * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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};

int main(){
	char buff[100];
	int s = 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");
		fflush(stdout);
		x += dx[dir];
		y += dy[dir];
		gets(buff);
		update();
	};

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

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

	};

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

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

	auto move_ = [&](){
		vector<vector<pair<int,int>>> last(50, vector<pair<int,int>>(50, {-1,-1}));
		queue<pair<int,int>> q;
		q.push(st.top().first);

		while(q.size()){
			auto pos = q.front(); q.pop();
			if(pos == st.top().first) break;
			//cerr << pos.first << " " << pos.second << " " << dir;


			int x_ = pos.first;
			int y_ = pos.second;
			for(int k__=0; k__<4; k__++){
				int new_x = x_+ dx[k__];
				int new_y = y_ + dy[k__];
				if(field[new_x][new_y] == 1 || field[new_x][new_y] == 3){
					if(last[new_x][new_y] == last[0][0] ){
						last[new_x][new_y] = {x_,y_};
						q.push({x_,y_});
					}
				}
			}
		}
		while(pair<int,int>{x,y} != st.
			top().first){
			auto p = last[x][y];
			if(p == pair<int,int>{x+dx[(dir+1)&3], y+dy[(dir+1)&3]}){
				turn_right();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+3)&3], y+dy[(dir+3)&3]}){
				turn_left();
				go_foward();
			}else if(p == pair<int,int>{x+dx[(dir+2)&3], y+dy[(dir+2)&3]}){
				go_backward();
			}else{
				go_foward();
			}
		}

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

	gets(buff);
	while(true){
		int d = update();
		if(d<=0) break;
		go_foward();
	}

	while(true){
		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]);
			}
		}

		if(st.top() == pair<pair<int,int>,int>{{x,y}, dir}){
			st.pop();
			go_foward();
			continue;
		}else{
			move_();
		}
	}
	return 0;
}
0