Submission #9040521


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int M, R;
int keys[4][3] = {
	{7, 8, 9}, 
	{4, 5, 6},
	{1, 2, 3},
	{0, -1, -1}
};
int dist[4][3][101010];
bool vis[4][3][101010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> M >> R;

	rep(y, 0, 4) rep(x, 0, 3) rep(mo, 0, M) dist[y][x][mo] = inf;

	queue<vector<int>> que;
	que.push({3, 0, 0});
	dist[3][0][0] = 0;

	while (!que.empty()) {
		auto v = que.front(); que.pop();

		int y = v[0];
		int x = v[1];
		int mo = v[2];

		rep(d, 0, 4) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (0 <= xx and xx < 3 and 0 <= yy and yy < 4) {
				if (keys[yy][xx] < 0) continue;

				chmin(dist[yy][xx][mo], dist[y][x][mo] + 1);
				if (!vis[yy][xx][mo]) {
					vis[yy][xx][mo] = true;
					que.push({yy, xx, mo});
				}
			}
		}

		int mo2 = (mo * 10 + keys[y][x]) % M;
		chmin(dist[y][x][mo2], dist[y][x][mo] + 1);
		if (!vis[y][x][mo2]) {
			vis[y][x][mo2] = true;
			que.push({ y, x, mo2 });
		}
	}

	int ans = inf;
	rep(y, 0, 4) rep(x, 0, 3) chmin(ans, dist[y][x][R]);
	cout << ans << endl;
}





Submission Info

Submission Time
Task D - テンキー (Tenkey)
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2470 Byte
Status
Exec Time 159 ms
Memory 24452 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
Subtask1 30 / 30 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt
Subtask2 70 / 70 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, 02-33.txt, 02-34.txt, 02-35.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt 112 ms 13312 KB
01-02.txt 111 ms 13312 KB
01-03.txt 112 ms 13312 KB
01-04.txt 111 ms 13312 KB
01-05.txt 112 ms 13312 KB
01-06.txt 113 ms 13312 KB
01-07.txt 110 ms 13312 KB
01-08.txt 114 ms 13312 KB
01-09.txt 111 ms 13312 KB
01-10.txt 113 ms 13312 KB
01-11.txt 112 ms 13312 KB
01-12.txt 111 ms 13312 KB
01-13.txt 110 ms 13312 KB
01-14.txt 112 ms 13312 KB
02-01.txt 2 ms 2432 KB
02-02.txt 3 ms 2560 KB
02-03.txt 2 ms 2432 KB
02-04.txt 2 ms 2560 KB
02-05.txt 2 ms 2432 KB
02-06.txt 2 ms 2432 KB
02-07.txt 114 ms 15744 KB
02-08.txt 82 ms 15872 KB
02-09.txt 129 ms 20996 KB
02-10.txt 93 ms 17540 KB
02-11.txt 43 ms 9344 KB
02-12.txt 26 ms 5760 KB
02-13.txt 127 ms 22020 KB
02-14.txt 116 ms 21380 KB
02-15.txt 13 ms 4352 KB
02-16.txt 127 ms 22916 KB
02-17.txt 35 ms 7936 KB
02-18.txt 54 ms 11264 KB
02-19.txt 141 ms 22920 KB
02-20.txt 140 ms 21764 KB
02-21.txt 144 ms 22916 KB
02-22.txt 2 ms 2560 KB
02-23.txt 3 ms 2560 KB
02-24.txt 145 ms 24068 KB
02-25.txt 144 ms 24452 KB
02-26.txt 143 ms 24068 KB
02-27.txt 137 ms 22276 KB
02-28.txt 135 ms 23812 KB
02-29.txt 144 ms 24196 KB
02-30.txt 132 ms 23428 KB
02-31.txt 129 ms 17536 KB
02-32.txt 159 ms 23172 KB
02-33.txt 114 ms 14208 KB
02-34.txt 103 ms 14208 KB
02-35.txt 115 ms 14336 KB
sample-01.txt 111 ms 13312 KB
sample-02.txt 2 ms 2432 KB