oj.uz

답안 #158871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
158871 2019-10-19T08:56:45 Z ioane Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 12268 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define LL int
#define MP make_pair
#define PB push_back
#define I insert

const LL N = 1600000;

using namespace std;

LL n, m, i, j, k, l, r, t, x, y;
LL a[N], dp[N], x3[20];
LL boo[200000000];
char c;

int main(){
	x3[0] = 1;
	for ( i = 1; i < 20; ++i ){
		x3[i] = x3[i-1] * 3;
	}
	
	cin >> n >> m;
	for ( i = 0; i < (1<<n); ++i ){
		cin >> c;
		a[i] = c - '0';
	}
	k = min(n,13);
	for ( i = 0; i < x3[k]; ++i ){
		t = i;
		l = 0;
		for ( j = 0; j < k; ++j ){
			r = t % 3;
			if ( r == 2 ){
				dp[i] = dp[i - x3[j]] + dp[i - 2*x3[j]];
				l = -100;
				break;
			}
			l += (1<<(j)) * r;
			t /= 3;
		}
		if ( l >= 0 ){
			dp[i] = a[l];
		}
		//cout << i << " " << dp[i] << "  " << l << endl;
	}
	
	while ( m-- ){
		t = 0;
		for ( i = 0; i < k; ++i ){
			cin >> c;
			t *= 3;
			if ( c == '?' ) t += 2;
			else t += c - '0';
		}
		
		cout << dp[t] << endl;
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Execution timed out 2051 ms 3312 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Execution timed out 2051 ms 3312 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Incorrect 346 ms 12268 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 7 ms 632 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 7 ms 632 KB Output is correct
7 Correct 7 ms 632 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Execution timed out 2051 ms 3312 KB Time limit exceeded
12 Halted 0 ms 0 KB -