oj.uz

Submission #287342

# Submission time Handle Problem Language Result Execution time Memory
287342 2020-08-31T16:02:31 Z luciocf Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 495 ms 65540 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -