oj.uz

Submission #213485

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

using namespace std;

int N, L, Q, T;
int arr[1<<20];
int dp[60000];
vector<short> ternary[60000];
int pows[20];
int pre[1000005];
vector<short> 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 24 ms 25344 KB Output is correct
2 Correct 23 ms 25472 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 23 ms 25344 KB Output is correct
6 Correct 23 ms 25344 KB Output is correct
7 Correct 23 ms 25344 KB Output is correct
8 Correct 23 ms 25412 KB Output is correct
9 Correct 22 ms 25344 KB Output is correct
10 Correct 23 ms 25344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25344 KB Output is correct
2 Correct 23 ms 25472 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 23 ms 25344 KB Output is correct
6 Correct 23 ms 25344 KB Output is correct
7 Correct 23 ms 25344 KB Output is correct
8 Correct 23 ms 25412 KB Output is correct
9 Correct 22 ms 25344 KB Output is correct
10 Correct 23 ms 25344 KB Output is correct
11 Runtime error 540 ms 65540 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 24 ms 25344 KB Output is correct
2 Correct 23 ms 25472 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 23 ms 25344 KB Output is correct
6 Correct 23 ms 25344 KB Output is correct
7 Correct 23 ms 25344 KB Output is correct
8 Correct 23 ms 25412 KB Output is correct
9 Correct 22 ms 25344 KB Output is correct
10 Correct 23 ms 25344 KB Output is correct
11 Runtime error 540 ms 65540 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 24 ms 25344 KB Output is correct
2 Correct 23 ms 25472 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 23 ms 25344 KB Output is correct
6 Correct 23 ms 25344 KB Output is correct
7 Correct 23 ms 25344 KB Output is correct
8 Correct 23 ms 25412 KB Output is correct
9 Correct 22 ms 25344 KB Output is correct
10 Correct 23 ms 25344 KB Output is correct
11 Execution timed out 2102 ms 36600 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25344 KB Output is correct
2 Correct 23 ms 25472 KB Output is correct
3 Correct 23 ms 25216 KB Output is correct
4 Correct 23 ms 25216 KB Output is correct
5 Correct 23 ms 25344 KB Output is correct
6 Correct 23 ms 25344 KB Output is correct
7 Correct 23 ms 25344 KB Output is correct
8 Correct 23 ms 25412 KB Output is correct
9 Correct 22 ms 25344 KB Output is correct
10 Correct 23 ms 25344 KB Output is correct
11 Runtime error 540 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -