Submission #158880

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158880	2019-10-19T09:25:14 Z	ioane	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	2000 ms	65536 KB

snake_escaping

#include<bits/stdc++.h>
#define F first
#define S second
#define LL int
#define MP make_pair
#define PB push_back
#define I insert

const LL N = 1600000;

using namespace std;

LL n, m, i, j, k, l, r, t, x, y, w, ans;
LL a[N], dp[130][N], x3[20];
char c;

int main(){
	x3[0] = 1;
	for ( i = 1; i < 20; ++i ){
		x3[i] = x3[i-1] * 3;
	}
	
	cin >> n >> m;
	for ( i = 0; i < (1<<n); ++i ){
		cin >> c;
		a[i] = c - '0';
	}
	k = min(n,13);
	for ( w = 0; w < (1<<(n-k)); ++w ){
		for ( i = 0; i < x3[k]; ++i ){
			t = i;
			l = 0;
			for ( j = 0; j < k; ++j ){
				r = t % 3;
				if ( r == 2 ){
					dp[w][i] = dp[w][i - x3[j]] + dp[w][i - 2*x3[j]];
					l = -100;
					break;
				}
				l += (1<<(j)) * r;
				t /= 3;
			}
			if ( l >= 0 ){
				dp[w][i] = a[l+(w<<(k))];
			}
			
			//cout << i << " " << dp[i] << "  " << l << endl;
		}
	}
	
	while ( m-- ){
		t = 0;
		for ( i = 0; i < k; ++i ){
			cin >> c;
			t *= 3;
			if ( c == '?' ) t += 2;
			else t += c - '0';
		}
		ans = 0;
		for ( i = 0; i < (1<<(n-k)); ++i ){
			ans += dp[i][t];
		}
		cout << ans << endl;
	}
	
	return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	6 ms	508 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	7 ms	632 KB	Output is correct
9	Correct	7 ms	632 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	6 ms	508 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	7 ms	632 KB	Output is correct
9	Correct	7 ms	632 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct
11	Execution timed out	2053 ms	3156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	6 ms	508 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	7 ms	632 KB	Output is correct
9	Correct	7 ms	632 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct
11	Execution timed out	2053 ms	3156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	6 ms	508 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	7 ms	632 KB	Output is correct
9	Correct	7 ms	632 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct
11	Runtime error	323 ms	65536 KB	Execution killed with signal 9 (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	7 ms	632 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	6 ms	632 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	6 ms	508 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	7 ms	632 KB	Output is correct
9	Correct	7 ms	632 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct
11	Execution timed out	2053 ms	3156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-