Submission #1113339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1113339	2024-11-16T12:01:33 Z	vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	2000 ms	15436 KB

snake_escaping

// Problem: B - Snake Escaping
// Contest: Virtual Judge - Variety
// URL: https://vjudge.net/contest/671976#problem/B
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// 
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 20, SPLIT = 20;

int n, q, mask[1<<N];
string vals;

int dp[2][1<<N][N];
int sos[2][1<<N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> q >> vals;
	for (int i = 0; i < (1<<n); i++)
		mask[i] = vals[i] - '0';
	
	for (int msk = 0; msk < (1<<n); msk++) {
		dp[0][msk][0] = mask[msk];
		dp[1][msk][0] = mask[msk];
		for (int i = 1; i <= n; i++) {
			dp[0][msk][i] += dp[0][msk][i-1];
			dp[1][msk][i] += dp[1][msk][i-1];
			if (msk & (1 << (i-1)))
				dp[0][msk][i] += dp[0][msk ^ (1 << (i-1))][i-1];
			else
				dp[1][msk][i] += dp[1][msk ^ (1 << (i-1))][i-1];
		}
		sos[0][msk] = dp[0][msk][n];
		sos[1][msk] = dp[1][msk][n];
	}
	
	while (q--) {
		string b;
		cin >> b;
		int c_marks=0, c_0=0, c_1=0;
		for (char c : b)
			if (c == '?')
				c_marks++;
			else if (c == '1')
				c_1++;
			else
				c_0++;
		
		
		if (c_marks <= SPLIT) {
			int init = 0;
			for (int i = 0; i < n; i++)
				if (b[i] == '1')
					init |= (1 << (n-i-1));
			// bruteforce
			int ans = 0;
			for (int msk = 0; msk < (1 << c_marks); msk++) {
				int final = init;
				int idx = 0;
				for (int i = 0; i < n; i++)
					if (b[i] == '?') {
						if (msk&(1<<idx))
							final |= (1 << (n-i-1));
						idx++;
					}
				ans += mask[final];	
				cerr << bitset<N>(msk) << endl;
			}
			cerr <<endl;
			cout << ans << '\n';
			continue;
		}
		
		
	}
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1100 KB	Output is correct
2	Correct	172 ms	1732 KB	Output is correct
3	Correct	26 ms	592 KB	Output is correct
4	Correct	28 ms	848 KB	Output is correct
5	Correct	189 ms	1900 KB	Output is correct
6	Correct	54 ms	848 KB	Output is correct
7	Correct	60 ms	840 KB	Output is correct
8	Execution timed out	2059 ms	15436 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1100 KB	Output is correct
2	Correct	172 ms	1732 KB	Output is correct
3	Correct	26 ms	592 KB	Output is correct
4	Correct	28 ms	848 KB	Output is correct
5	Correct	189 ms	1900 KB	Output is correct
6	Correct	54 ms	848 KB	Output is correct
7	Correct	60 ms	840 KB	Output is correct
8	Execution timed out	2059 ms	15436 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1100 KB	Output is correct
2	Correct	172 ms	1732 KB	Output is correct
3	Correct	26 ms	592 KB	Output is correct
4	Correct	28 ms	848 KB	Output is correct
5	Correct	189 ms	1900 KB	Output is correct
6	Correct	54 ms	848 KB	Output is correct
7	Correct	60 ms	840 KB	Output is correct
8	Execution timed out	2059 ms	15436 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1100 KB	Output is correct
2	Correct	172 ms	1732 KB	Output is correct
3	Correct	26 ms	592 KB	Output is correct
4	Correct	28 ms	848 KB	Output is correct
5	Correct	189 ms	1900 KB	Output is correct
6	Correct	54 ms	848 KB	Output is correct
7	Correct	60 ms	840 KB	Output is correct
8	Execution timed out	2059 ms	15436 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	1100 KB	Output is correct
2	Correct	172 ms	1732 KB	Output is correct
3	Correct	26 ms	592 KB	Output is correct
4	Correct	28 ms	848 KB	Output is correct
5	Correct	189 ms	1900 KB	Output is correct
6	Correct	54 ms	848 KB	Output is correct
7	Correct	60 ms	840 KB	Output is correct
8	Execution timed out	2059 ms	15436 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-