oj.uz

Submission #287836

# Submission time Handle Problem Language Result Execution time Memory
287836 2020-09-01T03:54:28 Z MatheusLealV Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 314 ms 24440 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -