답안 #287343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287343	2020-08-31T16:03:03 Z	luciocf	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	487 ms	65540 KB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int maxn = 13;

int n, q;
char v[1<<maxn];

int b[1<<maxn];

unordered_map<int, int> dp[1<<maxn];

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> q;

	for (int i = 0; i < (1<<n); i++)
	{
		cin >> v[i];
		v[i] = (int)(v[i]-'0');
	}

	for (int i = 1; i < (1<<n); i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i&(1<<j))
			{
				b[i] = j;
				break;
			}
		}
	}

	for (int fixo = (1<<n)-1; fixo >= 0; fixo--)
	{
		dp[fixo][0] = v[fixo];

		int mask = ((1<<n)-1)^fixo;

		vector<int> sub;

		for (int outro = mask; outro > 0; outro = (outro-1)&mask)
			sub.push_back(outro);

		reverse(sub.begin(), sub.end());

		for (auto outro: sub)
			dp[fixo][outro] = dp[fixo][outro^(1<<b[outro])] + dp[fixo|(1<<b[outro])][outro^(1<<b[outro])];
	}

	while (q--)
	{
		int fixo = 0, outro = 0;

		for (int i = 0; i < n; i++)
		{
			char c;
			cin >> c;

			if (c == '?') outro += (1<<(n-i-1));
			else if (c == '1') fixo += (1<<(n-i-1));
		}

		cout << dp[fixo][outro] << "\n";
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	3328 KB	Output is correct
2	Correct	10 ms	3456 KB	Output is correct
3	Correct	10 ms	3328 KB	Output is correct
4	Correct	10 ms	3328 KB	Output is correct
5	Correct	11 ms	3456 KB	Output is correct
6	Correct	11 ms	3328 KB	Output is correct
7	Correct	11 ms	3328 KB	Output is correct
8	Correct	11 ms	3456 KB	Output is correct
9	Correct	10 ms	3328 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	3328 KB	Output is correct
2	Correct	10 ms	3456 KB	Output is correct
3	Correct	10 ms	3328 KB	Output is correct
4	Correct	10 ms	3328 KB	Output is correct
5	Correct	11 ms	3456 KB	Output is correct
6	Correct	11 ms	3328 KB	Output is correct
7	Correct	11 ms	3328 KB	Output is correct
8	Correct	11 ms	3456 KB	Output is correct
9	Correct	10 ms	3328 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Correct	359 ms	7416 KB	Output is correct
12	Correct	366 ms	7160 KB	Output is correct
13	Correct	415 ms	6372 KB	Output is correct
14	Correct	400 ms	6524 KB	Output is correct
15	Correct	393 ms	7544 KB	Output is correct
16	Correct	448 ms	6648 KB	Output is correct
17	Correct	487 ms	6648 KB	Output is correct
18	Correct	270 ms	8568 KB	Output is correct
19	Correct	367 ms	5368 KB	Output is correct
20	Correct	375 ms	7160 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	3328 KB	Output is correct
2	Correct	10 ms	3456 KB	Output is correct
3	Correct	10 ms	3328 KB	Output is correct
4	Correct	10 ms	3328 KB	Output is correct
5	Correct	11 ms	3456 KB	Output is correct
6	Correct	11 ms	3328 KB	Output is correct
7	Correct	11 ms	3328 KB	Output is correct
8	Correct	11 ms	3456 KB	Output is correct
9	Correct	10 ms	3328 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Correct	359 ms	7416 KB	Output is correct
12	Correct	366 ms	7160 KB	Output is correct
13	Correct	415 ms	6372 KB	Output is correct
14	Correct	400 ms	6524 KB	Output is correct
15	Correct	393 ms	7544 KB	Output is correct
16	Correct	448 ms	6648 KB	Output is correct
17	Correct	487 ms	6648 KB	Output is correct
18	Correct	270 ms	8568 KB	Output is correct
19	Correct	367 ms	5368 KB	Output is correct
20	Correct	375 ms	7160 KB	Output is correct
21	Runtime error	230 ms	65540 KB	Execution killed with signal 9
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	3328 KB	Output is correct
2	Correct	10 ms	3456 KB	Output is correct
3	Correct	10 ms	3328 KB	Output is correct
4	Correct	10 ms	3328 KB	Output is correct
5	Correct	11 ms	3456 KB	Output is correct
6	Correct	11 ms	3328 KB	Output is correct
7	Correct	11 ms	3328 KB	Output is correct
8	Correct	11 ms	3456 KB	Output is correct
9	Correct	10 ms	3328 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Runtime error	4 ms	2048 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	3328 KB	Output is correct
2	Correct	10 ms	3456 KB	Output is correct
3	Correct	10 ms	3328 KB	Output is correct
4	Correct	10 ms	3328 KB	Output is correct
5	Correct	11 ms	3456 KB	Output is correct
6	Correct	11 ms	3328 KB	Output is correct
7	Correct	11 ms	3328 KB	Output is correct
8	Correct	11 ms	3456 KB	Output is correct
9	Correct	10 ms	3328 KB	Output is correct
10	Correct	12 ms	3328 KB	Output is correct
11	Correct	359 ms	7416 KB	Output is correct
12	Correct	366 ms	7160 KB	Output is correct
13	Correct	415 ms	6372 KB	Output is correct
14	Correct	400 ms	6524 KB	Output is correct
15	Correct	393 ms	7544 KB	Output is correct
16	Correct	448 ms	6648 KB	Output is correct
17	Correct	487 ms	6648 KB	Output is correct
18	Correct	270 ms	8568 KB	Output is correct
19	Correct	367 ms	5368 KB	Output is correct
20	Correct	375 ms	7160 KB	Output is correct
21	Runtime error	230 ms	65540 KB	Execution killed with signal 9
22	Halted	0 ms	0 KB	-