oj.uz

Submission #42164

# Submission time Handle Problem Language Result Execution time Memory
42164 2018-02-23T05:38:18 Z fest Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 2000 ms 584 KB 
// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 20, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int ones[N], dp[2][2][1 << N], cost[2][1 << N], qs[N];

bool built[1 << N];

int n;

inline int rev(int x) {
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (x & (1 << i)) continue;
		ret |= (1 << i);
	} 
	return ret;
}

void build(int ty) {
	for (int mask = 0; mask < (1 << n); mask++) {
		dp[ty][0][mask] += cost[ty][mask];
		if (mask & 1) dp[ty][0][mask] += cost[ty][mask ^ 1];
	}		
	for (int bit = 1; bit < n; bit++) {
		int j = (bit & 1);
		for (int mask = 0; mask < (1 << n); mask++) {
			dp[ty][j][mask] = dp[ty][j ^ 1][mask];
			if (mask & (1 << bit)) dp[ty][j][mask] += dp[ty][j ^ 1][mask ^ (1 << bit)];
		}
	}
}

inline int calc(int ty) {
	int ret = 0;
	int alw = 0;
	int mask = 0;
	for (int i = 0; i < n; i++) {
		if (qs[i] == 2) alw |= (1 << i);
		if (qs[i] == 1) mask |= (1 << i);
	}
	for (int pod = mask; ; pod = (pod - 1) & mask) {
		if (built[pod]) ret -= dp[ty][(n - 1) & 1][alw | pod];
		else ret += dp[ty][(n - 1) & 1][alw | pod];
	}	
	return abs(ret);
} 

int main() {
  
	int q;
	cin >> n >> q;
	scanf("\n");
	for (int i = 0; i < (1 << n); i++) {
		char x = getchar();
		cost[0][i] = (int)(x - '0');
		cost[1][rev(i)] = (int)(x - '0');
	} 
	for (int mask = 0; mask < (1 << n); mask++) built[mask] = (__builtin_popcount(mask) & 1);
	build(0);
	build(1);
	while (q--) {
		getchar();
		int zer = 0, one = 0, que = 0;
		for (int i = n - 1; i >= 0; i--) {
			char x = getchar();
			if (x == '?') qs[i] = 2, que++;
			if (x == '1') qs[i] = 1, one++;
			if (x == '0') qs[i] = 0, zer++;
		}
		if (!one) {
			int ret = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ret |= (1 << i);
			}
			printf("%d\n", dp[0][(n - 1) & 1][ret]);
			continue;
		}
		if (!zer) {
			int ret = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ret |= (1 << i);
			}
			printf("%d\n", dp[1][(n - 1) & 1][ret]);
			continue;
		}
		if (que < 7) {
			int ans = 0;
			int mask = 0;
			int alw = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) mask |= (1 << i); 
				if (qs[i] == 1) alw |= (1 << i);
			}
			for (int pod = mask; ; pod = (pod - 1) & mask) {
				ans += cost[0][alw | pod];
				if (!pod) break;
			}
			printf("%d\n", ans);
			continue;
		}
		if (one < 7) {
			printf("%d\n", calc(0));
			continue;
		}
		for (int i = 0; i < n; i++) if (qs[i] < 2) qs[i] ^= 1;
		printf("%d\n", calc(1));
	}
	return 0;	
}

Compilation message

snake_escaping.cpp: In function 'void FREOPEN()':
snake_escaping.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
snake_escaping.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:89:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n");
             ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Execution timed out 2033 ms 584 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Execution timed out 2033 ms 584 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Execution timed out 2033 ms 584 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Execution timed out 2033 ms 584 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Execution timed out 2033 ms 584 KB Time limit exceeded
8 Halted 0 ms 0 KB -