Submission #66868

#	Time	Username	Problem	Language	Result	Execution time	Memory
66868		ekrem	Snake Escaping (JOI18_snake_escaping)	C++98	12 / 100	978 ms	14316 KiB

snake_escaping

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, m, a[N], dp[N];
char c;

int f(int bit){
	if(dp[bit] != -1)
		return dp[bit];
	int yed = bit, crp = 1, ckr = -1;
	while(yed){
		if(yed%3 == 2){
			ckr = crp;
			break;
		}
		crp *= 3;
		yed /= 3;
	}
	if(ckr == -1){
		yed = bit;
		int say = 0, cvp = 0;
		while(yed){
			cvp += (1<<say)*(yed%3);
			say++;
			yed /= 3;
		}
		return dp[bit] = a[cvp];
	}
	return dp[bit] = f(bit - ckr) + f(bit - ckr - ckr);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof dp);
	scanf("%d %d",&n ,&m);
	for(int i = 0; i < (1<<n); i++){
		scanf(" %c",&c);
		a[i] = c - '0';
	}
	for(int i = 1; i <= m; i++){
		int bit = 0;
		for(int i = 1; i <= n; i++){
			scanf(" %c" ,&c);
			bit *= 3;
			bit += (c == '?') ? 2 : c - '0';
		}
		printf("%d\n",f(bit));
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
   ~~~~~^~~~~~~~~~
snake_escaping.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c" ,&c);
    ~~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25