oj.uz

Submission #287339

# Submission time Handle Problem Language Result Execution time Memory
287339 2020-08-31T15:56:14 Z luciocf Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 515 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 13;

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 = 0; 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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3712 KB Output is correct
4 Correct 12 ms 3584 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 13 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 12 ms 3584 KB Output is correct
10 Correct 12 ms 3584 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3712 KB Output is correct
4 Correct 12 ms 3584 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 13 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 12 ms 3584 KB Output is correct
10 Correct 12 ms 3584 KB Output is correct
11 Correct 393 ms 18332 KB Output is correct
12 Correct 410 ms 18040 KB Output is correct
13 Correct 476 ms 17144 KB Output is correct
14 Correct 442 ms 17368 KB Output is correct
15 Correct 478 ms 18296 KB Output is correct
16 Correct 510 ms 17400 KB Output is correct
17 Correct 515 ms 17528 KB Output is correct
18 Correct 304 ms 19320 KB Output is correct
19 Correct 363 ms 16380 KB Output is correct
20 Correct 455 ms 17912 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3712 KB Output is correct
4 Correct 12 ms 3584 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 13 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 12 ms 3584 KB Output is correct
10 Correct 12 ms 3584 KB Output is correct
11 Correct 393 ms 18332 KB Output is correct
12 Correct 410 ms 18040 KB Output is correct
13 Correct 476 ms 17144 KB Output is correct
14 Correct 442 ms 17368 KB Output is correct
15 Correct 478 ms 18296 KB Output is correct
16 Correct 510 ms 17400 KB Output is correct
17 Correct 515 ms 17528 KB Output is correct
18 Correct 304 ms 19320 KB Output is correct
19 Correct 363 ms 16380 KB Output is correct
20 Correct 455 ms 17912 KB Output is correct
21 Runtime error 270 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3712 KB Output is correct
4 Correct 12 ms 3584 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 13 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 12 ms 3584 KB Output is correct
10 Correct 12 ms 3584 KB Output is correct
11 Runtime error 3 ms 1920 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3712 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3712 KB Output is correct
4 Correct 12 ms 3584 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 12 ms 3584 KB Output is correct
7 Correct 13 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 12 ms 3584 KB Output is correct
10 Correct 12 ms 3584 KB Output is correct
11 Correct 393 ms 18332 KB Output is correct
12 Correct 410 ms 18040 KB Output is correct
13 Correct 476 ms 17144 KB Output is correct
14 Correct 442 ms 17368 KB Output is correct
15 Correct 478 ms 18296 KB Output is correct
16 Correct 510 ms 17400 KB Output is correct
17 Correct 515 ms 17528 KB Output is correct
18 Correct 304 ms 19320 KB Output is correct
19 Correct 363 ms 16380 KB Output is correct
20 Correct 455 ms 17912 KB Output is correct
21 Runtime error 270 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -