oj.uz

답안 #42155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42155 2018-02-23T05:12:14 Z fest Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 65536 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 built[1 << N], ones[21], dp[2][2][1 << N], cost[2][1 << N], qs[21];

int n;

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 % 2;
		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)];
		}
	}
}

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

int main() {
  
	int q;
	cin >> n >> q;
	scanf("\n");
	for (int i = 0; i < (1 << n); i++) {
		char x;
		scanf("%c", &x);
		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);
	build(0);
	build(1);
	while (q--) {
		scanf("\n");
		int zer = 0, one = 0, que = 0;
		for (int i = n - 1; i >= 0; i--) {
			char x;
			scanf("%c", &x);
			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) % 2][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) % 2][ret]);
			continue;
		}
		if (que < 8) {
			int ans = 0;
			int r = 0;
			int alw = 0;
			for (int i = 0; i < n; i++) {
				if (qs[i] == 2) ones[r++] = i; 
				if (qs[i] == 1) alw |= (1 << i);
			}
			for (int mask = 0; mask < (1 << que); mask++) {
				int ret = alw;
				for (int i = 0; i < r; i++) {
					if (mask & (1 << i)) ret |= (1 << ones[i]);
				}
				ans += cost[0][ret];
			}
			printf("%d\n", ans);
			continue;
		}
		if (one < 8) {
			printf("%d\n", calc(0, one));
			continue;
		}
		for (int i = 0; i < n; i++) if (qs[i] < 2) qs[i] ^= 1;
		printf("%d\n", calc(1, zer));
	}
	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:91:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n");
             ^
snake_escaping.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &x);
                  ^
snake_escaping.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n");
              ^
snake_escaping.cpp:106:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%c", &x);
                   ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 3 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 612 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 3 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 612 KB Output is correct
11 Correct 740 ms 7612 KB Output is correct
12 Correct 711 ms 18180 KB Output is correct
13 Correct 730 ms 27948 KB Output is correct
14 Correct 758 ms 37236 KB Output is correct
15 Correct 1213 ms 38348 KB Output is correct
16 Correct 862 ms 38348 KB Output is correct
17 Correct 908 ms 38348 KB Output is correct
18 Correct 606 ms 39240 KB Output is correct
19 Correct 666 ms 39240 KB Output is correct
20 Correct 709 ms 39240 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 3 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 612 KB Output is correct
11 Correct 740 ms 7612 KB Output is correct
12 Correct 711 ms 18180 KB Output is correct
13 Correct 730 ms 27948 KB Output is correct
14 Correct 758 ms 37236 KB Output is correct
15 Correct 1213 ms 38348 KB Output is correct
16 Correct 862 ms 38348 KB Output is correct
17 Correct 908 ms 38348 KB Output is correct
18 Correct 606 ms 39240 KB Output is correct
19 Correct 666 ms 39240 KB Output is correct
20 Correct 709 ms 39240 KB Output is correct
21 Correct 863 ms 39240 KB Output is correct
22 Correct 853 ms 53148 KB Output is correct
23 Correct 1055 ms 65536 KB Output is correct
24 Correct 1012 ms 65536 KB Output is correct
25 Correct 972 ms 65536 KB Output is correct
26 Correct 1228 ms 65536 KB Output is correct
27 Correct 1169 ms 65536 KB Output is correct
28 Correct 699 ms 65536 KB Output is correct
29 Correct 863 ms 65536 KB Output is correct
30 Correct 907 ms 65536 KB Output is correct
31 Correct 1483 ms 65536 KB Output is correct
32 Correct 1125 ms 65536 KB Output is correct
33 Correct 876 ms 65536 KB Output is correct
34 Correct 946 ms 65536 KB Output is correct
35 Correct 1166 ms 65536 KB Output is correct
36 Correct 809 ms 65536 KB Output is correct
37 Correct 818 ms 65536 KB Output is correct
38 Correct 831 ms 65536 KB Output is correct
39 Correct 969 ms 65536 KB Output is correct
40 Correct 961 ms 65536 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 3 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 612 KB Output is correct
11 Correct 327 ms 65536 KB Output is correct
12 Correct 271 ms 65536 KB Output is correct
13 Correct 294 ms 65536 KB Output is correct
14 Correct 348 ms 65536 KB Output is correct
15 Correct 289 ms 65536 KB Output is correct
16 Correct 334 ms 65536 KB Output is correct
17 Correct 360 ms 65536 KB Output is correct
18 Correct 258 ms 65536 KB Output is correct
19 Correct 271 ms 65536 KB Output is correct
20 Correct 274 ms 65536 KB Output is correct
21 Correct 297 ms 65536 KB Output is correct
22 Correct 372 ms 65536 KB Output is correct
23 Correct 284 ms 65536 KB Output is correct
24 Correct 303 ms 65536 KB Output is correct
25 Correct 340 ms 65536 KB Output is correct
26 Correct 272 ms 65536 KB Output is correct
27 Correct 269 ms 65536 KB Output is correct
28 Correct 270 ms 65536 KB Output is correct
29 Correct 298 ms 65536 KB Output is correct
30 Correct 302 ms 65536 KB Output is correct
31 Correct 281 ms 65536 KB Output is correct
32 Correct 325 ms 65536 KB Output is correct
33 Correct 363 ms 65536 KB Output is correct
34 Correct 279 ms 65536 KB Output is correct
35 Correct 349 ms 65536 KB Output is correct
36 Correct 340 ms 65536 KB Output is correct
37 Correct 307 ms 65536 KB Output is correct
38 Correct 322 ms 65536 KB Output is correct
39 Correct 328 ms 65536 KB Output is correct
40 Correct 327 ms 65536 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 3 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 3 ms 612 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 612 KB Output is correct
11 Correct 740 ms 7612 KB Output is correct
12 Correct 711 ms 18180 KB Output is correct
13 Correct 730 ms 27948 KB Output is correct
14 Correct 758 ms 37236 KB Output is correct
15 Correct 1213 ms 38348 KB Output is correct
16 Correct 862 ms 38348 KB Output is correct
17 Correct 908 ms 38348 KB Output is correct
18 Correct 606 ms 39240 KB Output is correct
19 Correct 666 ms 39240 KB Output is correct
20 Correct 709 ms 39240 KB Output is correct
21 Correct 863 ms 39240 KB Output is correct
22 Correct 853 ms 53148 KB Output is correct
23 Correct 1055 ms 65536 KB Output is correct
24 Correct 1012 ms 65536 KB Output is correct
25 Correct 972 ms 65536 KB Output is correct
26 Correct 1228 ms 65536 KB Output is correct
27 Correct 1169 ms 65536 KB Output is correct
28 Correct 699 ms 65536 KB Output is correct
29 Correct 863 ms 65536 KB Output is correct
30 Correct 907 ms 65536 KB Output is correct
31 Correct 1483 ms 65536 KB Output is correct
32 Correct 1125 ms 65536 KB Output is correct
33 Correct 876 ms 65536 KB Output is correct
34 Correct 946 ms 65536 KB Output is correct
35 Correct 1166 ms 65536 KB Output is correct
36 Correct 809 ms 65536 KB Output is correct
37 Correct 818 ms 65536 KB Output is correct
38 Correct 831 ms 65536 KB Output is correct
39 Correct 969 ms 65536 KB Output is correct
40 Correct 961 ms 65536 KB Output is correct
41 Correct 327 ms 65536 KB Output is correct
42 Correct 271 ms 65536 KB Output is correct
43 Correct 294 ms 65536 KB Output is correct
44 Correct 348 ms 65536 KB Output is correct
45 Correct 289 ms 65536 KB Output is correct
46 Correct 334 ms 65536 KB Output is correct
47 Correct 360 ms 65536 KB Output is correct
48 Correct 258 ms 65536 KB Output is correct
49 Correct 271 ms 65536 KB Output is correct
50 Correct 274 ms 65536 KB Output is correct
51 Correct 297 ms 65536 KB Output is correct
52 Correct 372 ms 65536 KB Output is correct
53 Correct 284 ms 65536 KB Output is correct
54 Correct 303 ms 65536 KB Output is correct
55 Correct 340 ms 65536 KB Output is correct
56 Correct 272 ms 65536 KB Output is correct
57 Correct 269 ms 65536 KB Output is correct
58 Correct 270 ms 65536 KB Output is correct
59 Correct 298 ms 65536 KB Output is correct
60 Correct 302 ms 65536 KB Output is correct
61 Correct 281 ms 65536 KB Output is correct
62 Correct 325 ms 65536 KB Output is correct
63 Correct 363 ms 65536 KB Output is correct
64 Correct 279 ms 65536 KB Output is correct
65 Correct 349 ms 65536 KB Output is correct
66 Correct 340 ms 65536 KB Output is correct
67 Correct 307 ms 65536 KB Output is correct
68 Correct 322 ms 65536 KB Output is correct
69 Correct 328 ms 65536 KB Output is correct
70 Correct 327 ms 65536 KB Output is correct
71 Correct 1640 ms 65536 KB Output is correct
72 Correct 1581 ms 65536 KB Output is correct
73 Execution timed out 2039 ms 65536 KB Time limit exceeded
74 Halted 0 ms 0 KB -