Submission #1130209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130209		iframe_	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	321 ms	26068 KiB

snake_escaping

#include <algorithm>
#include <iostream>
#include <array>

int *a[21], d[1<<21];

using ll = long long;

std::array<ll, 2> b[1000000];
int res[1000000];

void dfs(int l, int r, int d, int p, int s){
	if(!s)
		for(; l<r; ++l) res[b[l][1]] = a[d][0];

	else{
		int s1 = r, s2 = r;

		for(int i=r-1; i>=l; --i){
			if(((b[i][0] >> (p*2)) & 3) >= 2) s2 = i;
			if(((b[i][0] >> (p*2)) & 3) >= 1) s1 = i;
		}

		if(l != s1){
			for(int i=0; i<s; ++i)
				a[d+1][i] = a[d][i];
			dfs(l, s1, d+1, p-1, s/2);
		}

		if(s1 != s2){
			for(int i=0; i<s; ++i)
				a[d+1][i] = a[d][i+s];
			dfs(s1, s2, d+1, p-1, s/2);
		}

		if(s2 != r){
			for(int i=0; i<s; ++i)
				a[d+1][i] = a[d][i] + a[d][i+s];
			dfs(s2, r, d+1, p-1, s/2);
		}
	}
}

int main(){
	std::cin.tie(0) -> sync_with_stdio(0);

	int l, q; std::cin >> l >> q;

	a[0] = d;
	for(int s=1<<l, p=1; s; ++p, s/=2)
		a[p] = a[p-1]+s;

	for(int i=0; i<1<<l; ++i){
		char c; std::cin >> c;
		a[0][i] = c-'0';
	}

	for(int i=0; i<q; ++i){
		b[i][1] = i;
		for(int j=0; j<l; ++j){
			char c; std::cin >> c;
			int m = c == '?' ? 2 : c - '0';
			b[i][0] |= m << ((l-j-1)*2);
		}
	}

	std::sort(b, b+q);

	dfs(0, q, 0, l-1, 1<<(l-1));

	for(int i=0; i<q; ++i) std::cout << res[i] << '\n';
}

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