oj.uz

Submission #886847

# Submission time Handle Problem Language Result Execution time Memory
886847 2023-12-13T04:00:03 Z socho Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 16400 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef vector<int> VI;
typedef set<int> SI;
typedef map<int, int> MII;
typedef pair<int, int> PII;

#define A first
#define B second
#define SZ(x) int(x.size())
#define PB push_back
#define FR(i, a, b) for (int i = (a); i < (b); i++)
#define FOR(i, n) FR(i, 0, n)
#define RF(i, a, b) for (int i = (a); i >= (b); i--)
#define FRA(a, x) for (auto a: (x))

template <typename T> inline void set_min(T &a, T b) {if(b < a) a = b;}
template <typename T> inline void set_max(T &a, T b) {if(b > a) a = b;}

int n, q;
string se;
const int MXN = 20;
int dp[1<<MXN];
int dp2[1<<MXN];
int val[1<<MXN];

int ms[MXN];
int p;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> q;
	cin >> se;
	
	FOR(i, 1<<n) {
		val[i] = (se[i] - '0');
		dp[i] = dp2[i] = (se[i] - '0');
	}
	
	FOR(b, n) {
		FOR(i, 1<<n) {
			if (i & (1 << b)) dp[i] += dp[i ^ (1 << b)];
			else dp2[i] += dp2[i ^ (1 << b)];
		}
	}
	
	string s;
	FOR(_, q) {
		cin >> s;
		reverse(s.begin(), s.end());
		
		int n0 = 0, n1 = 0, nq = 0;
		FRA(x, s) {
			if (x == '?') nq++;
			else if (x == '0') n0++;
			else n1++;
		}
		
		int ans = 0;
		if (nq > 6) {
			// just add over the bitmasks
			int main = 0;
			FOR(i, n) {
				if (s[i] == '?') ms[p++] = i;
				else if (s[i] == '1') main += (1 << i);
			}
			FOR(i, 1<<nq) {
				int p = main;
				FOR(j, nq) {
					if (i & (1 << j)) p += (1 << ms[j]);
				}
				ans += val[p];
			}
		}
		else if (n0 <= 6) {
			// 0011??
			// super(001100)
			// -super(011100)
			// -super(101100)
			// +super(111100)
			int main = 0;
			FOR(i, n) {
				if (s[i] == '0') ms[p++] = i;
				else if (s[i] == '1') main += (1 << i);
			}
			FOR(i, 1<<n0) {
				int p = main;
				FOR(j, n0) {
					if (i & (1 << j)) {
						p += (1 << ms[j]);
					}
				}
				if (__builtin_popcount(i) % 2 == 0) ans += dp2[p];
				else ans -= dp2[p];
			}
		}
		else { // n1 <= 6
			// 0011??
			// sub(001111)
			// -sub(001011)
			// -sub(000111)
			// +sub(000011)
			int main = 0;
			FOR(i, n) {
				if (s[i] == '1') ms[p++] = i;
				else if (s[i] == '?') main += (1 << i);
			}
			FOR(i, 1<<n1) {
				int p = main;
				FOR(j, n1) {
					if (i & (1 << j)) p += (1 << ms[j]);
				}
				if ((n1 - __builtin_popcount(i)) % 2 == 0) ans += dp[p];
				else ans -= dp[p];
			}
		}
		cout << ans << '\n';
		p = 0;
		
	}
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4568 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 36 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4568 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 36 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 182 ms 8336 KB Output is correct
12 Correct 954 ms 8324 KB Output is correct
13 Correct 479 ms 7644 KB Output is correct
14 Correct 320 ms 7444 KB Output is correct
15 Correct 236 ms 8536 KB Output is correct
16 Correct 277 ms 7660 KB Output is correct
17 Correct 420 ms 7592 KB Output is correct
18 Execution timed out 2039 ms 5100 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4568 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 36 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 182 ms 8336 KB Output is correct
12 Correct 954 ms 8324 KB Output is correct
13 Correct 479 ms 7644 KB Output is correct
14 Correct 320 ms 7444 KB Output is correct
15 Correct 236 ms 8536 KB Output is correct
16 Correct 277 ms 7660 KB Output is correct
17 Correct 420 ms 7592 KB Output is correct
18 Execution timed out 2039 ms 5100 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4568 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 36 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 1793 ms 16400 KB Output is correct
12 Execution timed out 2021 ms 15720 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4568 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 36 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 182 ms 8336 KB Output is correct
12 Correct 954 ms 8324 KB Output is correct
13 Correct 479 ms 7644 KB Output is correct
14 Correct 320 ms 7444 KB Output is correct
15 Correct 236 ms 8536 KB Output is correct
16 Correct 277 ms 7660 KB Output is correct
17 Correct 420 ms 7592 KB Output is correct
18 Execution timed out 2039 ms 5100 KB Time limit exceeded
19 Halted 0 ms 0 KB -