oj.uz

Submission #213487

# Submission time Handle Problem Language Result Execution time Memory
213487 2020-03-26T01:35:01 Z AQT Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 65544 KB 
#include <bits/stdc++.h>

using namespace std;

int N, L, Q, T;
int arr[1<<20];
int dp[60000];
vector<char> ternary[60000];
int pows[20];
int pre[1000005];
vector<char> qu[1000005];
int ans[1000005];

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> L >> Q;
	N = 1<<L;
	for(int m = 0; m<N; m++){
		char c;
		cin >> c;
		arr[m] = c-'0';
	}
	int H = L/2;
	T = 1;
	pows[0] = 1;
	for(int k = 0; k<H; k++){
		T *= 3;
		pows[k+1] = pows[k] * 3;
	}
	for(int m = 0; m<T; m++){
		int temp = m;
		for(int k = 0; k<H; k++){
			ternary[m].emplace_back(temp%3);
			temp /= 3;
		}
	}
	for(int q = 1; q<=Q; q++){
		int t = 0;
		for(int i = 0; i<L; i++){
			char c;
			cin >> c;
			if(c == '?'){
				qu[q].emplace_back(2);
			}
			else{
				qu[q].emplace_back(c-'0');
			}
		}
		for(int k = 0; k<H; k++){
			t *= 3;
			t += qu[q][k];
		}
		reverse(qu[q].begin(), qu[q].end());
		pre[q] = t;
	}
	for(int m = 0; m<1<<(L-H); m++){
		fill(dp, dp+T, 0);
		for(int t = 0; t<T; t++){
			bool has2 = 0;
			int temp = 0;
			for(int h = 0; h<H; h++){
				if(ternary[t][h] == 2){
					has2 = 1;
					dp[t] = dp[t-pows[h]] + dp[t-pows[h]*2];
					break;
				}
				temp += (1<<h)*ternary[t][h];
			}
			if(!has2){
				dp[t] = arr[(temp<<(L-H)) + m];
			}
		}
		for(int q = 1; q<=Q; q++){
			bool good = 1;
			for(int b = 0; b<L-H; b++){
				if(qu[q][b] == 2 || qu[q][b] == ((m>>b)&1)){
					
				}
				else{
					good = 0;
					break;
				}
			}
			if(good){
				ans[q] += dp[pre[q]];
			}
		}
	}
	for(int q = 1; q<=Q; q++){
		cout << ans[q] << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25216 KB Output is correct
2 Correct 21 ms 25344 KB Output is correct
3 Correct 19 ms 25344 KB Output is correct
4 Correct 20 ms 25344 KB Output is correct
5 Correct 19 ms 25344 KB Output is correct
6 Correct 20 ms 25344 KB Output is correct
7 Correct 19 ms 25344 KB Output is correct
8 Correct 19 ms 25344 KB Output is correct
9 Correct 19 ms 25344 KB Output is correct
10 Correct 19 ms 25344 KB Output is correct
11 Correct 1785 ms 34424 KB Output is correct
12 Correct 1882 ms 34424 KB Output is correct
13 Correct 1449 ms 34424 KB Output is correct
14 Correct 1796 ms 34424 KB Output is correct
15 Execution timed out 2101 ms 34168 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

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