Submission #1128578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128578		Alihan_8	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2041 ms	49416 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, q; cin >> n >> q;
	
	string s; cin >> s;
	
	for ( auto &v: s ) v -= '0';
	
	vector <int> pw(n + 1, 1);
	
	for ( int i = 1; i <= n; i++ ){
		pw[i] = pw[i - 1] * 3;
	}
	
	int B = min(n, 7), m = n - B;
	
	vector <string> qu(q);
	vector <int> val(q), lst(q);
	
	for ( int i = 0; i < q; i++ ){
		string t; cin >> t;
		
		qu[i] = t;
		
		for ( int j = 0; j < m; j++ ){
			val[i] = val[i] + pw[j] * (t[j] == '?' ? 2 : t[j] - '0');
		}
		
		for ( int j = n - 1; j >= m; j-- ){
			lst[i] = lst[i] * 3 + (t[j] == '?' ? 2 : t[j] - '0');
		}
	}
	
	vector <int> f(pw[m]);
	
	for ( int mask = 0; mask < pw[m]; mask++ ){
		for ( int i = 0; i < m; i++ ){
			f[mask] = f[mask] * 2 + mask / pw[i] % 3;
		}
	}
	
	vector <int> ans(q);
	
	for ( int lf = 0; lf < (1 << B); lf++ ){
		vector <int> is(pw[B]);
		
		for ( int mask = 0; mask < (1 << B); mask++ ){
			int cnt = 0;
			
			for ( int i = 0; i < n; i++ ){
				int b = lf >> i & 1;
				
				if ( mask >> i & 1 ) cnt = cnt + pw[i] * 2;
				else cnt = cnt + pw[i] * b;
			}
			
			is[cnt] = 1;
		}
		
		int cur = 0;
		
		for ( int i = 0; i < B; i++ ) cur = cur * 2 + (lf >> i & 1);
		
		vector <int> dp(pw[m]);
		
		for ( int mask = 0; mask < pw[m]; mask++ ){
			bool has_q = false;
			
			for ( int i = 0; i < m; i++ ){
				int b = mask / pw[i] % 3;
				
				if ( b == 2 ){
					dp[mask] = dp[mask - pw[i]] + dp[mask - pw[i] * 2];
					has_q = 1; break;
				}
			}
			
			if ( !has_q ){
				int x = (f[mask] << B) + cur;
				
				dp[mask] = s[x];
			}
		}
		
		for ( int i = 0; i < q; i++ ){
			ans[i] += dp[val[i]] * is[lst[i]];
		}
	}
	
	for ( auto &x: ans ) cout << x << '\n';
}

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