Submission #256768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256768	2020-08-03T07:49:42 Z	임성재(#5038)	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	343 ms	15524 KB

snake_escaping

#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int l, q;
int dp[1600010];
string s;

int main() {
	fast;

	cin >> l >> q;
	cin >> s;

	int mx = 1;
	for(int i=0; i<l; i++) {
		mx *= 3;
	}

	mx;

	for(int i=0; i<mx; i++) dp[i] = -1;

	for(int i=0; i<(1<<l); i++) {
		int b = 0;
		for(int j=l-1; j>=0; j--) {
			b *= 3;
			if(i & (1<<j)) b += 1;
		}

		dp[b] = s[i] - '0';
		//cout << b << " " << dp[b] << endl;
	}

	for(int i=0; i<mx; i++) {
		
		int b = 1;
		for(int j=l-1; j>=0; j--) {
			if((i / b) % 3 == 2) {
				dp[i] = dp[i - b] + dp[i - 2*b];
				//cout << i << "=" << i-2*b << "+" << i-b << endl;
				break;
			}

			b *= 3;
		}

		//cout << dp[i] << "\n";
	}

	while(q--) {
		string t;

		cin >> t;

		int b = 0;

		for(int i=0; i<l; i++) {
			b *= 3;
			if(t[i] == '?') b += 2;
			else b += t[i] - '0';
		}

		cout << dp[b] << "\n";
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:35:4: warning: statement has no effect [-Wunused-value]
  mx;
    ^

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	616 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	616 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	218 ms	4576 KB	Output is correct
12	Correct	226 ms	4336 KB	Output is correct
13	Correct	194 ms	3448 KB	Output is correct
14	Correct	205 ms	3576 KB	Output is correct
15	Correct	214 ms	4596 KB	Output is correct
16	Correct	218 ms	3912 KB	Output is correct
17	Correct	211 ms	3704 KB	Output is correct
18	Correct	165 ms	5756 KB	Output is correct
19	Correct	164 ms	2552 KB	Output is correct
20	Correct	221 ms	4328 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	616 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	218 ms	4576 KB	Output is correct
12	Correct	226 ms	4336 KB	Output is correct
13	Correct	194 ms	3448 KB	Output is correct
14	Correct	205 ms	3576 KB	Output is correct
15	Correct	214 ms	4596 KB	Output is correct
16	Correct	218 ms	3912 KB	Output is correct
17	Correct	211 ms	3704 KB	Output is correct
18	Correct	165 ms	5756 KB	Output is correct
19	Correct	164 ms	2552 KB	Output is correct
20	Correct	221 ms	4328 KB	Output is correct
21	Correct	268 ms	10616 KB	Output is correct
22	Correct	285 ms	10744 KB	Output is correct
23	Correct	264 ms	9848 KB	Output is correct
24	Correct	263 ms	9664 KB	Output is correct
25	Correct	268 ms	11640 KB	Output is correct
26	Correct	293 ms	10160 KB	Output is correct
27	Correct	295 ms	10104 KB	Output is correct
28	Correct	211 ms	12664 KB	Output is correct
29	Correct	195 ms	8568 KB	Output is correct
30	Correct	272 ms	10748 KB	Output is correct
31	Correct	307 ms	10616 KB	Output is correct
32	Correct	289 ms	10872 KB	Output is correct
33	Correct	243 ms	9464 KB	Output is correct
34	Correct	274 ms	9848 KB	Output is correct
35	Correct	343 ms	10232 KB	Output is correct
36	Correct	194 ms	8588 KB	Output is correct
37	Correct	264 ms	10616 KB	Output is correct
38	Correct	196 ms	8568 KB	Output is correct
39	Correct	270 ms	9848 KB	Output is correct
40	Correct	258 ms	9592 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	616 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Runtime error	18 ms	15524 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	2 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	616 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	640 KB	Output is correct
9	Correct	2 ms	512 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	218 ms	4576 KB	Output is correct
12	Correct	226 ms	4336 KB	Output is correct
13	Correct	194 ms	3448 KB	Output is correct
14	Correct	205 ms	3576 KB	Output is correct
15	Correct	214 ms	4596 KB	Output is correct
16	Correct	218 ms	3912 KB	Output is correct
17	Correct	211 ms	3704 KB	Output is correct
18	Correct	165 ms	5756 KB	Output is correct
19	Correct	164 ms	2552 KB	Output is correct
20	Correct	221 ms	4328 KB	Output is correct
21	Correct	268 ms	10616 KB	Output is correct
22	Correct	285 ms	10744 KB	Output is correct
23	Correct	264 ms	9848 KB	Output is correct
24	Correct	263 ms	9664 KB	Output is correct
25	Correct	268 ms	11640 KB	Output is correct
26	Correct	293 ms	10160 KB	Output is correct
27	Correct	295 ms	10104 KB	Output is correct
28	Correct	211 ms	12664 KB	Output is correct
29	Correct	195 ms	8568 KB	Output is correct
30	Correct	272 ms	10748 KB	Output is correct
31	Correct	307 ms	10616 KB	Output is correct
32	Correct	289 ms	10872 KB	Output is correct
33	Correct	243 ms	9464 KB	Output is correct
34	Correct	274 ms	9848 KB	Output is correct
35	Correct	343 ms	10232 KB	Output is correct
36	Correct	194 ms	8588 KB	Output is correct
37	Correct	264 ms	10616 KB	Output is correct
38	Correct	196 ms	8568 KB	Output is correct
39	Correct	270 ms	9848 KB	Output is correct
40	Correct	258 ms	9592 KB	Output is correct
41	Runtime error	18 ms	15524 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

Submission #256768

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