oj.uz

Submission #288683

# Submission time Handle Problem Language Result Execution time Memory
288683 2020-09-01T18:40:32 Z luciocf Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 493 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];
 
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);
 
		sort(sub.begin(), sub.end());
 
		for (auto outro: sub)
		{
			int p = 0, q = 0;

			if (dp[fixo].find(outro^(1<<b[outro])) != dp[fixo].end())
				p = dp[fixo][outro^(1<<b[outro])];

			if (dp[fixo|(1<<b[outro])].find(outro^(1<<b[outro])) != dp[fixo].end())
				q = dp[fixo|(1<<b[outro])][outro^(1<<b[outro])];

			dp[fixo][outro] = p+q;
		}
	}
 
	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 15 ms 3584 KB Output is correct
2 Correct 14 ms 3584 KB Output is correct
3 Correct 14 ms 3584 KB Output is correct
4 Correct 14 ms 3584 KB Output is correct
5 Correct 14 ms 3584 KB Output is correct
6 Correct 15 ms 3584 KB Output is correct
7 Correct 15 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 15 ms 3584 KB Output is correct
10 Correct 15 ms 3584 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3584 KB Output is correct
2 Correct 14 ms 3584 KB Output is correct
3 Correct 14 ms 3584 KB Output is correct
4 Correct 14 ms 3584 KB Output is correct
5 Correct 14 ms 3584 KB Output is correct
6 Correct 15 ms 3584 KB Output is correct
7 Correct 15 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 15 ms 3584 KB Output is correct
10 Correct 15 ms 3584 KB Output is correct
11 Correct 386 ms 18416 KB Output is correct
12 Correct 405 ms 17912 KB Output is correct
13 Correct 451 ms 17276 KB Output is correct
14 Correct 423 ms 17528 KB Output is correct
15 Correct 469 ms 18424 KB Output is correct
16 Correct 489 ms 17528 KB Output is correct
17 Correct 493 ms 17528 KB Output is correct
18 Correct 312 ms 19444 KB Output is correct
19 Correct 356 ms 16380 KB Output is correct
20 Correct 433 ms 18044 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3584 KB Output is correct
2 Correct 14 ms 3584 KB Output is correct
3 Correct 14 ms 3584 KB Output is correct
4 Correct 14 ms 3584 KB Output is correct
5 Correct 14 ms 3584 KB Output is correct
6 Correct 15 ms 3584 KB Output is correct
7 Correct 15 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 15 ms 3584 KB Output is correct
10 Correct 15 ms 3584 KB Output is correct
11 Correct 386 ms 18416 KB Output is correct
12 Correct 405 ms 17912 KB Output is correct
13 Correct 451 ms 17276 KB Output is correct
14 Correct 423 ms 17528 KB Output is correct
15 Correct 469 ms 18424 KB Output is correct
16 Correct 489 ms 17528 KB Output is correct
17 Correct 493 ms 17528 KB Output is correct
18 Correct 312 ms 19444 KB Output is correct
19 Correct 356 ms 16380 KB Output is correct
20 Correct 433 ms 18044 KB Output is correct
21 Runtime error 351 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 15 ms 3584 KB Output is correct
2 Correct 14 ms 3584 KB Output is correct
3 Correct 14 ms 3584 KB Output is correct
4 Correct 14 ms 3584 KB Output is correct
5 Correct 14 ms 3584 KB Output is correct
6 Correct 15 ms 3584 KB Output is correct
7 Correct 15 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 15 ms 3584 KB Output is correct
10 Correct 15 ms 3584 KB Output is correct
11 Runtime error 4 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 15 ms 3584 KB Output is correct
2 Correct 14 ms 3584 KB Output is correct
3 Correct 14 ms 3584 KB Output is correct
4 Correct 14 ms 3584 KB Output is correct
5 Correct 14 ms 3584 KB Output is correct
6 Correct 15 ms 3584 KB Output is correct
7 Correct 15 ms 3584 KB Output is correct
8 Correct 14 ms 3584 KB Output is correct
9 Correct 15 ms 3584 KB Output is correct
10 Correct 15 ms 3584 KB Output is correct
11 Correct 386 ms 18416 KB Output is correct
12 Correct 405 ms 17912 KB Output is correct
13 Correct 451 ms 17276 KB Output is correct
14 Correct 423 ms 17528 KB Output is correct
15 Correct 469 ms 18424 KB Output is correct
16 Correct 489 ms 17528 KB Output is correct
17 Correct 493 ms 17528 KB Output is correct
18 Correct 312 ms 19444 KB Output is correct
19 Correct 356 ms 16380 KB Output is correct
20 Correct 433 ms 18044 KB Output is correct
21 Runtime error 351 ms 65540 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -