답안 #287342

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

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int maxn = 14;

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

int b[1<<maxn];

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	13 ms	3968 KB	Output is correct
2	Correct	13 ms	3968 KB	Output is correct
3	Correct	13 ms	3968 KB	Output is correct
4	Correct	12 ms	3968 KB	Output is correct
5	Correct	13 ms	3968 KB	Output is correct
6	Correct	13 ms	3968 KB	Output is correct
7	Correct	13 ms	3968 KB	Output is correct
8	Correct	12 ms	3968 KB	Output is correct
9	Correct	12 ms	3840 KB	Output is correct
10	Correct	13 ms	3968 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	3968 KB	Output is correct
2	Correct	13 ms	3968 KB	Output is correct
3	Correct	13 ms	3968 KB	Output is correct
4	Correct	12 ms	3968 KB	Output is correct
5	Correct	13 ms	3968 KB	Output is correct
6	Correct	13 ms	3968 KB	Output is correct
7	Correct	13 ms	3968 KB	Output is correct
8	Correct	12 ms	3968 KB	Output is correct
9	Correct	12 ms	3840 KB	Output is correct
10	Correct	13 ms	3968 KB	Output is correct
11	Correct	369 ms	7928 KB	Output is correct
12	Correct	398 ms	7672 KB	Output is correct
13	Correct	451 ms	6904 KB	Output is correct
14	Correct	423 ms	6904 KB	Output is correct
15	Correct	485 ms	8056 KB	Output is correct
16	Correct	490 ms	7160 KB	Output is correct
17	Correct	495 ms	7032 KB	Output is correct
18	Correct	299 ms	9008 KB	Output is correct
19	Correct	337 ms	5880 KB	Output is correct
20	Correct	431 ms	7544 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	3968 KB	Output is correct
2	Correct	13 ms	3968 KB	Output is correct
3	Correct	13 ms	3968 KB	Output is correct
4	Correct	12 ms	3968 KB	Output is correct
5	Correct	13 ms	3968 KB	Output is correct
6	Correct	13 ms	3968 KB	Output is correct
7	Correct	13 ms	3968 KB	Output is correct
8	Correct	12 ms	3968 KB	Output is correct
9	Correct	12 ms	3840 KB	Output is correct
10	Correct	13 ms	3968 KB	Output is correct
11	Correct	369 ms	7928 KB	Output is correct
12	Correct	398 ms	7672 KB	Output is correct
13	Correct	451 ms	6904 KB	Output is correct
14	Correct	423 ms	6904 KB	Output is correct
15	Correct	485 ms	8056 KB	Output is correct
16	Correct	490 ms	7160 KB	Output is correct
17	Correct	495 ms	7032 KB	Output is correct
18	Correct	299 ms	9008 KB	Output is correct
19	Correct	337 ms	5880 KB	Output is correct
20	Correct	431 ms	7544 KB	Output is correct
21	Runtime error	276 ms	65540 KB	Execution killed with signal 9
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

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

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	3968 KB	Output is correct
2	Correct	13 ms	3968 KB	Output is correct
3	Correct	13 ms	3968 KB	Output is correct
4	Correct	12 ms	3968 KB	Output is correct
5	Correct	13 ms	3968 KB	Output is correct
6	Correct	13 ms	3968 KB	Output is correct
7	Correct	13 ms	3968 KB	Output is correct
8	Correct	12 ms	3968 KB	Output is correct
9	Correct	12 ms	3840 KB	Output is correct
10	Correct	13 ms	3968 KB	Output is correct
11	Correct	369 ms	7928 KB	Output is correct
12	Correct	398 ms	7672 KB	Output is correct
13	Correct	451 ms	6904 KB	Output is correct
14	Correct	423 ms	6904 KB	Output is correct
15	Correct	485 ms	8056 KB	Output is correct
16	Correct	490 ms	7160 KB	Output is correct
17	Correct	495 ms	7032 KB	Output is correct
18	Correct	299 ms	9008 KB	Output is correct
19	Correct	337 ms	5880 KB	Output is correct
20	Correct	431 ms	7544 KB	Output is correct
21	Runtime error	276 ms	65540 KB	Execution killed with signal 9
22	Halted	0 ms	0 KB	-