結果
問題 | No.331 CodeRunnerでやれ |
ユーザー |
|
提出日時 | 2016-06-10 03:13:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,554 bytes |
コンパイル時間 | 982 ms |
コンパイル使用メモリ | 96,936 KB |
実行使用メモリ | 95,136 KB |
平均クエリ数 | 0.76 |
最終ジャッジ日時 | 2024-07-16 23:56:46 |
合計ジャッジ時間 | 8,501 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 TLE * 1 -- * 14 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <set>#include <map>#include <queue>#include <tuple>#include <unordered_set>#include <unordered_map>#include <functional>#include <cstdio>#include <cassert>#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))using namespace std;const char FORWARD = 'F';const char BACKWARD = 'B';const char ROTATE_LEFT = 'L';const char ROTATE_RIGHT = 'R';typedef int direction_t;const direction_t RIGHT = 0;const direction_t UP = 1;const direction_t DOWN = 2;const direction_t LEFT = 3;direction_t rotate(direction_t dir, int deg) {return (dir + deg / 90) % 4;}pair<int,int> from_direction(direction_t dir) {switch (dir) {case RIGHT: return { 0, 1 };case UP: return { -1, 0 };case LEFT: return { 0, -1 };case DOWN: return { 1, 0 };}assert (false);}const int inf = 20151224;const int H = 37;const int W = 37;int main() {array<array<char,W>,H> field = {};array<array<int,W>,H> seen = {};int y = H/2, x = W/2;direction_t d = RIGHT;auto nearest_unkown = [&]() {array<array<bool,W>,H> used = {};queue<tuple<int,int,direction_t> > que;used[y][x] = true;que.emplace(y, x, -1);while (not que.empty()) {int y, x; direction_t fst; tie(y, x, fst) = que.front();repeat (d,4) {int dy, dx; tie(dy, dx) = from_direction(d);int ny = y + dy;int nx = x + dx;direction_t nfst = fst == -1 ? d : fst;switch (field[ny][nx]) {case '\0':return nfst;case '#':break;case '.':if (not used[ny][nx]) {used[ny][nx] = true;que.emplace(ny, nx, nfst);}break;}}}assert (false);};auto think = [&](int input) {if (input == inf) return FORWARD;if (seen[y][x] != 0xf) return ROTATE_LEFT;direction_t fst = nearest_unkown();returnfst == rotate(d, 0) ? FORWARD :fst == rotate(d, 90) ? ROTATE_LEFT :fst == rotate(d, 270) ? ROTATE_RIGHT :BACKWARD;};char last_cmd = '\0';;int last_input;int input = -1;while (true) {last_input = input;cin >> input;if (not cin) break;if (last_cmd == FORWARD and last_input >= 1) { int dy, dx; tie(dy, dx) = from_direction(d); y += dy; x += dx; }if (last_cmd == BACKWARD and input == last_input + 1) { int dy, dx; tie(dy, dx) = from_direction(d); y -= dy; x -= dx; }if (last_cmd == ROTATE_LEFT) d = rotate(d, 90);if (last_cmd == ROTATE_RIGHT) d = rotate(d, 270);int dy, dx; tie(dy, dx) = from_direction(d);repeat (i,input+2) {int ny = y + i * dy;int nx = x + i * dx;if (ny < 0 or H <= ny or nx < 0 or W < nx) break;if (i == input+1) {field[y][x] = '#';} else {field[y][x] = '.';seen[y][x] |= 1 << d;}}char cmd = think(input);cout << cmd << endl;cout.flush();last_cmd = cmd;}return 0;}