oj.uz

Submission #213484

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

using namespace std;

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

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++){
		string s;
		cin >> s;
		int t = 0;
		for(int i = 0; i<L; i++){
			if(s[i] == '?'){
				qu[q].emplace_back(2);
			}
			else{
				qu[q].emplace_back(s[i]-'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 8 ms 3072 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 7 ms 3328 KB Output is correct
10 Correct 7 ms 3328 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3072 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 7 ms 3328 KB Output is correct
10 Correct 7 ms 3328 KB Output is correct
11 Runtime error 38 ms 12536 KB Execution killed with signal 11 (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 8 ms 3072 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 7 ms 3328 KB Output is correct
10 Correct 7 ms 3328 KB Output is correct
11 Runtime error 38 ms 12536 KB Execution killed with signal 11 (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 8 ms 3072 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 7 ms 3328 KB Output is correct
10 Correct 7 ms 3328 KB Output is correct
11 Correct 1769 ms 14840 KB Output is correct
12 Correct 1848 ms 14840 KB Output is correct
13 Correct 1457 ms 14840 KB Output is correct
14 Correct 1775 ms 14840 KB Output is correct
15 Execution timed out 2100 ms 14584 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3072 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 7 ms 3328 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 7 ms 3328 KB Output is correct
10 Correct 7 ms 3328 KB Output is correct
11 Runtime error 38 ms 12536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -