Submission #41569

#	Time	Username	Problem	Language	Result	Execution time	Memory
41569		fest	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	948 ms	65536 KiB

snake_escaping

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 1594323, inf = 1e9 * 2, MOD = (int)1e9 + 7, M = 13;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int n;

int ans[N], dp[N], pos[N], p[21], cost[(1 << 20)], qs[20];

vector<pair<int, int> > have[(1 << (20 - M))];

int main() {
  
	FREOPEN();
	int q;
	cin >> n >> q;
	scanf("\n");
	for (int i = 0; i < (1 << n); i++) {
		char x;
		scanf("%c", &x);
		cost[i] = int(x - '0');
	} 
	p[0] = 1;
	for (int i = 1; i <= n; i++) p[i] = p[i - 1] * 3;
	for (int qq = 1; qq <= q; qq++) {
		scanf("\n");
		for (int i = n - 1; i >= 0; i--) {
			char x;
			scanf("%c", &x);
		  if (x == '?') qs[i] = 2;
		  else qs[i] = int(x - '0');
		}
		if (n <= M) {
			int go = 0;
			for (int i = n - 1; i >= 0; i--) {
				go += qs[i] * p[i];
			}
			have[0].pb({go, qq});
		}
		else {
			int go = 0;
			for (int i = M - 1; i >= 0; i--) {
				go += qs[i] * p[i];
			} 
			for (int mask = 0; mask < (1 << (20 - M)); mask++) {
				bool ok = 1;
				for (int i = 19; i >= M; i--) {
					if (qs[i] == 2) continue;
					int bit = ((mask & (1 << (i - M))) > 0);
					if (bit != qs[i]) {
						ok = 0;
						break;
					}
				}
				if (ok) have[mask].pb({go, qq});
			}
		}
	}
	for (int x = 0; x < p[n]; x++) {
		int y = x;
		int two = 0;
		int posi = 0;
		while (y) {
			if (y % 3 == 2) {
				two = -posi - 1;
				break;
			}
			if (y % 3 == 1) two |= (1 << posi);
			y /= 3;
			posi++;
		}
		pos[x] = two;
	}
	for (int mask = 0; mask < (1 << (20 - M)); mask++) {
		if (have[mask].empty()) continue;
		for (int x = 0; x < p[n]; x++) {	
			if (pos[x] >= 0) {
				int ret = (mask << M);
				ret |= pos[x];
				dp[x] = cost[ret];
			}
			else {
				dp[x] = dp[x - p[-pos[x] - 1]] + dp[x - p[-pos[x] - 1] - p[-pos[x] - 1]];
	  	}
	  }
		for (auto i : have[mask]) {
			ans[i.S] += dp[i.F];
		}
	}
	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	return 0;	
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:49:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n");
             ^
snake_escaping.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &x);
                  ^
snake_escaping.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n");
              ^
snake_escaping.cpp:61:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c", &x);
                   ^

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