oj.uz

답안 #534363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534363 2022-03-08T06:04:57 Z rk42745417 Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 2 ms 332 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

signed main() {
	int l, q;
	cin >> l >> q;
	vector<int> arr(1 << l), dp(1 << l), dp2(1 << l);
	{
		string s;
		cin >> s;
		for(int i = 0; i < (1 << l); i++)
			arr[i] = dp[i] = dp2[i] = s[i] - '0';
	}
	for(int i = 0; i < l; i++)
		for(int j = 0; j < (1 << l); j++)
			if(j >> i & 1)
				dp[j] += dp[j ^ (1 << i)];
	for(int i = 0; i < l; i++)
		for(int j = 0; j < (1 << l); j++)
			if(j >> i & 1 ^ 1)
				dp2[j] += dp2[j ^ (1 << i)];
	function<int(const string&, int, int)> dfs = [&](const string &s, int n, int cur) {
		if(n == l)
			return arr[cur];
		if(s[n] == '?')
			return dfs(s, n + 1, cur) + dfs(s, n + 1, cur | (1 << n));
		if(s[n] == '1')
			return dfs(s, n + 1, cur | (1 << n));
		return dfs(s, n + 1, cur);
	};
	function<int(const string &s, int, int, int)> dfs2 = [&](const string &s, int n, int cur, int cnt) {
		if(n == l)
			return dp[cur] * (cnt % 2 ? -1 : 1);
		if(s[n] == '?')
			return dfs2(s, n + 1, cur | (1 << n), cnt);
		if(s[n] == '0')
			return dfs2(s, n + 1, cur, cnt);
		return dfs2(s, n + 1, cur | (1 << n), cnt) + dfs2(s, n + 1, cur, cnt + 1);
	};
	function<int(const string &s, int, int, int)> dfs3 = [&](const string &s, int n, int cur, int cnt) {
		if(n == l)
			return dp2[cur] * (cnt % 2 ? -1 : 1);
		if(s[n] == '?')
			return dfs3(s, n + 1, cur, cnt);
		if(s[n] == '1')
			return dfs3(s, n + 1, cur | (1 << n), cnt);
		return dfs3(s, n + 1, cur | (1 << n), cnt) + dfs3(s, n + 1, cur, cnt + 1);
	};

	while(q--) {
		string s;
		cin >> s;
		reverse(s.begin(), s.end());
		int cnt = 0, cnt2 = 0;
		for(char c : s) {
			cnt += c == '?';
			cnt2 += c == '1';
		}
		int cnt3 = l - (cnt + cnt2);
		if(cnt <= min(cnt3, cnt2))
			cout << dfs(s, 0, 0) << '\n';
		else if(cnt2 <= min(cnt, cnt3))
			cout << dfs2(s, 0, 0, 0) << '\n';
		else
			cout << dfs3(s, 0, 0, 0) << '\n';
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:56:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   56 |    if(j >> i & 1 ^ 1)
      |       ~~~~~~~^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -