답안 #287836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287836	2020-09-01T03:54:28 Z	MatheusLealV	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	314 ms	24440 KB

snake_escaping

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int, int> pii;
#define N 350010
 
int n, q;
string t;
int ans[1600000], pow3[30], cost[1600000];
int get_mask(int mask, int i){
	return (mask/pow3[i]) % 3;
}

bool vis[N];
void gen(int mask){
	if(vis[mask]) return;
	vis[mask] = 1;
	for(int i = 0; i < n; i++){
		int value = get_mask(mask, i);
		if(value == 2){
			int L = mask, R = mask;
			L += -2*pow3[i] + pow3[i];
			R += -2*pow3[i];
			gen(L);
			gen(R);
			cost[mask] += cost[L] + cost[R];
			break;
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>q;
	cin>>t;
	pow3[0] = 1;
	for(int i = 1; i < 30; i++) pow3[i] = (3*pow3[i-1]);
	for(int i = 0; i < (1<<n); i++){
		int mask = 0;
		for(int j= 0; j < n; j++){
			if(i & (1<<j)) mask += pow3[j];
		}
		cost[mask] += t[i]-'0';
	}
	for(int i = 0; i < pow3[n];i++) gen(i);
	while(q--){
		string s;
		int mask = 0;
		cin>>s;
		reverse(all(s));
		for(int i = 0; i < n; i++){
			if(s[i] == '1') mask += pow3[i];
			else if(s[i] == '?') mask += 2*pow3[i];
		}
		// gen(mask);
		cout<<cost[mask]<<"\n";
	}
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	252 ms	15480 KB	Output is correct
12	Correct	299 ms	14200 KB	Output is correct
13	Correct	257 ms	13432 KB	Output is correct
14	Correct	257 ms	13560 KB	Output is correct
15	Correct	253 ms	14584 KB	Output is correct
16	Correct	270 ms	13688 KB	Output is correct
17	Correct	272 ms	13688 KB	Output is correct
18	Correct	196 ms	15608 KB	Output is correct
19	Correct	229 ms	12624 KB	Output is correct
20	Correct	241 ms	14240 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	252 ms	15480 KB	Output is correct
12	Correct	299 ms	14200 KB	Output is correct
13	Correct	257 ms	13432 KB	Output is correct
14	Correct	257 ms	13560 KB	Output is correct
15	Correct	253 ms	14584 KB	Output is correct
16	Correct	270 ms	13688 KB	Output is correct
17	Correct	272 ms	13688 KB	Output is correct
18	Correct	196 ms	15608 KB	Output is correct
19	Correct	229 ms	12624 KB	Output is correct
20	Correct	241 ms	14240 KB	Output is correct
21	Incorrect	314 ms	24440 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Runtime error	10 ms	6180 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	640 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	252 ms	15480 KB	Output is correct
12	Correct	299 ms	14200 KB	Output is correct
13	Correct	257 ms	13432 KB	Output is correct
14	Correct	257 ms	13560 KB	Output is correct
15	Correct	253 ms	14584 KB	Output is correct
16	Correct	270 ms	13688 KB	Output is correct
17	Correct	272 ms	13688 KB	Output is correct
18	Correct	196 ms	15608 KB	Output is correct
19	Correct	229 ms	12624 KB	Output is correct
20	Correct	241 ms	14240 KB	Output is correct
21	Incorrect	314 ms	24440 KB	Output isn't correct
22	Halted	0 ms	0 KB	-