Submission #229700

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
229700	2020-05-05T23:45:24 Z	hanagasumi	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	372 ms	26232 KB

snake_escaping

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>

#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll

using namespace std;
typedef long long ll;

const int maxn = 1594323 + 100;
int dp[maxn];

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int L, q;
	cin >> L >> q;
	string s;
	cin >> s;
	int n = (1 << L);
	vector<int> step(L + 1, 1);
	for (int i = 1; i <= L; i++)
		step[i] = step[i - 1] * 3;
	for (int i = 0; i < maxn; i++) 
		dp[i] = 0;

	for (int i = 0; i < n; i++) {
		int ic = i, now = 0;;
		vector<int> have;
		for (int j = 0; j < L; j++) {
			have.pb(ic % 2);
			ic /= 2;
		}
		reverse(have.begin(), have.end());
		for (int j = 0; j < L; j++) {
			now = now * 3 + have[j];
		}
		dp[now] = s[i] - '0';
	}
	for (int i = 0; i < maxn; i++) {
		int pos = -1, ic = i;
		for (int j = 0; j < L; j++) {
			if(ic % 3 == 2) {
				pos = j;
				break;
			}
			ic /= 3;
		}
		if(pos == -1) 
			continue;
		dp[i] += dp[i - step[pos] * 1] + dp[i - step[pos] * 2];
	}
	for (int i = 0; i < q; i++) {
		string ask;
		cin >> ask;
		int now = 0;
		for (int j = 0; j < L; j++) {
			if(ask[j] == '0') 
				now = now * 3 + 0;
			if(ask[j] == '1') 
				now = now * 3 + 1;
			if(ask[j] == '?') 
				now = now * 3 + 2;
		}
		cout << dp[now] << '\n';
	}
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	6656 KB	Output is correct
2	Correct	20 ms	6656 KB	Output is correct
3	Correct	20 ms	6656 KB	Output is correct
4	Correct	21 ms	6528 KB	Output is correct
5	Correct	20 ms	6656 KB	Output is correct
6	Correct	20 ms	6528 KB	Output is correct
7	Correct	19 ms	6656 KB	Output is correct
8	Correct	19 ms	6656 KB	Output is correct
9	Correct	20 ms	6528 KB	Output is correct
10	Correct	19 ms	6644 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	6656 KB	Output is correct
2	Correct	20 ms	6656 KB	Output is correct
3	Correct	20 ms	6656 KB	Output is correct
4	Correct	21 ms	6528 KB	Output is correct
5	Correct	20 ms	6656 KB	Output is correct
6	Correct	20 ms	6528 KB	Output is correct
7	Correct	19 ms	6656 KB	Output is correct
8	Correct	19 ms	6656 KB	Output is correct
9	Correct	20 ms	6528 KB	Output is correct
10	Correct	19 ms	6644 KB	Output is correct
11	Correct	245 ms	21440 KB	Output is correct
12	Correct	251 ms	21004 KB	Output is correct
13	Correct	259 ms	20344 KB	Output is correct
14	Correct	256 ms	20344 KB	Output is correct
15	Correct	237 ms	21368 KB	Output is correct
16	Correct	262 ms	20472 KB	Output is correct
17	Correct	266 ms	20472 KB	Output is correct
18	Correct	204 ms	22392 KB	Output is correct
19	Correct	221 ms	19320 KB	Output is correct
20	Correct	245 ms	20988 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	6656 KB	Output is correct
2	Correct	20 ms	6656 KB	Output is correct
3	Correct	20 ms	6656 KB	Output is correct
4	Correct	21 ms	6528 KB	Output is correct
5	Correct	20 ms	6656 KB	Output is correct
6	Correct	20 ms	6528 KB	Output is correct
7	Correct	19 ms	6656 KB	Output is correct
8	Correct	19 ms	6656 KB	Output is correct
9	Correct	20 ms	6528 KB	Output is correct
10	Correct	19 ms	6644 KB	Output is correct
11	Correct	245 ms	21440 KB	Output is correct
12	Correct	251 ms	21004 KB	Output is correct
13	Correct	259 ms	20344 KB	Output is correct
14	Correct	256 ms	20344 KB	Output is correct
15	Correct	237 ms	21368 KB	Output is correct
16	Correct	262 ms	20472 KB	Output is correct
17	Correct	266 ms	20472 KB	Output is correct
18	Correct	204 ms	22392 KB	Output is correct
19	Correct	221 ms	19320 KB	Output is correct
20	Correct	245 ms	20988 KB	Output is correct
21	Correct	261 ms	24312 KB	Output is correct
22	Correct	280 ms	24632 KB	Output is correct
23	Correct	332 ms	23500 KB	Output is correct
24	Correct	297 ms	23288 KB	Output is correct
25	Correct	292 ms	25336 KB	Output is correct
26	Correct	319 ms	23800 KB	Output is correct
27	Correct	353 ms	23928 KB	Output is correct
28	Correct	235 ms	26232 KB	Output is correct
29	Correct	251 ms	22264 KB	Output is correct
30	Correct	275 ms	24492 KB	Output is correct
31	Correct	308 ms	24312 KB	Output is correct
32	Correct	328 ms	24440 KB	Output is correct
33	Correct	273 ms	23160 KB	Output is correct
34	Correct	326 ms	23300 KB	Output is correct
35	Correct	372 ms	23796 KB	Output is correct
36	Correct	190 ms	22264 KB	Output is correct
37	Correct	263 ms	24312 KB	Output is correct
38	Correct	256 ms	22392 KB	Output is correct
39	Correct	334 ms	23544 KB	Output is correct
40	Correct	299 ms	23356 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	6656 KB	Output is correct
2	Correct	20 ms	6656 KB	Output is correct
3	Correct	20 ms	6656 KB	Output is correct
4	Correct	21 ms	6528 KB	Output is correct
5	Correct	20 ms	6656 KB	Output is correct
6	Correct	20 ms	6528 KB	Output is correct
7	Correct	19 ms	6656 KB	Output is correct
8	Correct	19 ms	6656 KB	Output is correct
9	Correct	20 ms	6528 KB	Output is correct
10	Correct	19 ms	6644 KB	Output is correct
11	Runtime error	22 ms	16676 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	6656 KB	Output is correct
2	Correct	20 ms	6656 KB	Output is correct
3	Correct	20 ms	6656 KB	Output is correct
4	Correct	21 ms	6528 KB	Output is correct
5	Correct	20 ms	6656 KB	Output is correct
6	Correct	20 ms	6528 KB	Output is correct
7	Correct	19 ms	6656 KB	Output is correct
8	Correct	19 ms	6656 KB	Output is correct
9	Correct	20 ms	6528 KB	Output is correct
10	Correct	19 ms	6644 KB	Output is correct
11	Correct	245 ms	21440 KB	Output is correct
12	Correct	251 ms	21004 KB	Output is correct
13	Correct	259 ms	20344 KB	Output is correct
14	Correct	256 ms	20344 KB	Output is correct
15	Correct	237 ms	21368 KB	Output is correct
16	Correct	262 ms	20472 KB	Output is correct
17	Correct	266 ms	20472 KB	Output is correct
18	Correct	204 ms	22392 KB	Output is correct
19	Correct	221 ms	19320 KB	Output is correct
20	Correct	245 ms	20988 KB	Output is correct
21	Correct	261 ms	24312 KB	Output is correct
22	Correct	280 ms	24632 KB	Output is correct
23	Correct	332 ms	23500 KB	Output is correct
24	Correct	297 ms	23288 KB	Output is correct
25	Correct	292 ms	25336 KB	Output is correct
26	Correct	319 ms	23800 KB	Output is correct
27	Correct	353 ms	23928 KB	Output is correct
28	Correct	235 ms	26232 KB	Output is correct
29	Correct	251 ms	22264 KB	Output is correct
30	Correct	275 ms	24492 KB	Output is correct
31	Correct	308 ms	24312 KB	Output is correct
32	Correct	328 ms	24440 KB	Output is correct
33	Correct	273 ms	23160 KB	Output is correct
34	Correct	326 ms	23300 KB	Output is correct
35	Correct	372 ms	23796 KB	Output is correct
36	Correct	190 ms	22264 KB	Output is correct
37	Correct	263 ms	24312 KB	Output is correct
38	Correct	256 ms	22392 KB	Output is correct
39	Correct	334 ms	23544 KB	Output is correct
40	Correct	299 ms	23356 KB	Output is correct
41	Runtime error	22 ms	16676 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

Submission #229700

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0