oj.uz

Submission #287343

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

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

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

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

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

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