結果

問題 No.1152 10億ゲーム
ユーザー nikkukun
提出日時 2020-08-13 21:33:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,250 bytes
コンパイル時間 1,563 ms
コンパイル使用メモリ 168,936 KB
実行使用メモリ 51,888 KB
最終ジャッジ日時 2024-07-17 05:49:35
合計ジャッジ時間 8,035 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;

const int N = 100 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int vst[N][N][2];
int f[N][N][2], nxt[N][N][2]; // 0: first, 1: second

bool OK(int x, int y) {
	return x >= 0 && x <= 9 && y >= 0 && y <= 9;
}

// u is the one to move
int DFS(int u, int v, int op) {
	if (vst[u][v][op] == 1) return f[u][v][op];
	if (vst[u][v][op] == -1) return -1;

	f[u][v][op] = -1;
	vst[u][v][op] = -1;
	if (u == v) {
		f[u][v][op] = 0;
		vst[u][v][op] = 1;
	}

	int dir = -1;
	int nowf = op ? -INF : INF;
	for (int d = 0; d < 4; d++) {
		int ux = u / 10 + dx[d];
		int uy = u % 10 + dy[d];
		if (!OK(ux, uy)) continue;

		int tmp = DFS(v, ux * 10 + uy, op ^ 1);
		if (tmp == -1) continue;
		if (op == 0 && tmp < nowf)
			nowf = tmp, dir = d;
		if (op == 1 && tmp > nowf)
			nowf = tmp, dir = d;
	}
	if (dir != -1) {
		vst[u][v][op] = 1;
		f[u][v][op] = nowf + 1;
		nxt[u][v][op] = dir;
	}
	return f[u][v][op];
}

int GetPow(int x, int d) {
	int ret = 0;
	while (x % d == 0) {
		ret++;
		x /= d;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);

	memset(nxt, -1, sizeof(nxt));

	for (int t = 0; t < N * 10; t++) {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int op = 0; op <= 1; op++)
					if (vst[i][j][op] != 1)
						vst[i][j][op] = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int op = 0; op <= 1; op++)
					if (!vst[i][j][op])
						DFS(i, j, op);
	}
	// cout << clock() << endl;

	int u, v;
	cin >> u >> v;
	int ux = GetPow(u, 2), uy = GetPow(u, 5);
	int vx = GetPow(v, 2), vy = GetPow(v, 5);
	u = ux * 10 + uy;
	v = vx * 10 + vy;

	while (u != v) {
		int d = nxt[u][v][0];
		assert(d != -1);
		int ux = u / 10 + dx[d];
		int uy = u % 10 + dy[d];
		u = pow(2, ux) * pow(5, uy);
		cout << u << endl;
		cin >> v;
		vx = GetPow(v, 2), vy = GetPow(v, 5);
		u = ux * 10 + uy;
		v = vx * 10 + vy;
	}

	return 0;
}
0