oj.uz

Submission #130124

# Submission time Handle Problem Language Result Execution time Memory
130124 2019-07-14T04:26:49 Z qkxwsm Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 2000 ms 43336 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 1100013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
int arr[MAXN];
int sos[MAXN], sob[MAXN];
vi freq[3];
int ans;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> Q;
	string temps; cin >> temps;
	FOR(i, 0, (1 << N))
	{
		arr[i] = temps[i] - '0';
		sos[i] = arr[i];
		sob[i] = arr[i];
	}
	//compute answer if there were only 1s and ????s
	FOR(i, 0, N)
	{
		FOR(j, 0, (1 << N))
		{
			if (j & (1 << i))
			{
				sos[j] += sos[j - (1 << i)];
			}
			else
			{
				sob[j] += sob[j + (1 << i)];
			}
		}
	}
	while(Q--)
	{
		cin >> temps; reverse(ALL(temps));
		ans = 0;
		int tot = 0;
		FOR(i, 0, 3) freq[i].clear();
		FOR(i, 0, N)
		{
			int want = temps[i] - '0';
			if (temps[i] == '?') want = 2;
			freq[want].PB(i);
		}
		int mn = 0;
		FOR(i, 0, 3) if (SZ(freq[i]) < SZ(freq[mn])) mn = i;
		//now solve it in O(2^mn)
		if (mn == 2)
		{
			int idx = 0;
			for (int x : freq[1]) idx += (1 << x);
			FOR(i, 0, (1 << SZ(freq[2])))
			{
				int cidx = idx;
				FOR(j, 0, SZ(freq[2]))
				{
					if ((i & (1 << j)))
					{
						cidx += (1 << freq[2][j]);
					}
				}
				ans += arr[cidx];
			}
		}
		if (mn == 1)
		{
			int idx = 0;
			for (int x : freq[1]) idx += (1 << x);
			for (int x : freq[2]) idx += (1 << x);
			FOR(i, 0, (1 << SZ(freq[1])))
			{
				int cidx = idx;
				FOR(j, 0, SZ(freq[1]))
				{
					if ((i & (1 << j))) cidx -= (1 << freq[1][j]);
				}
				ans += ((__builtin_popcount(i) & 1) ? -1 : 1) * sos[cidx];
			}
		}
		if (mn == 0)
		{
			int idx = 0;
			for (int x : freq[1]) idx += (1 << x);
			FOR(i, 0, (1 << SZ(freq[0])))
			{
				int cidx = idx;
				FOR(j, 0, SZ(freq[0]))
				{
					if (i & (1 << j)) cidx += (1 << freq[0][j]);
				}
				ans += ((__builtin_popcount(i) & 1) ? -1 : 1) * sob[cidx];
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:75:7: warning: unused variable 'tot' [-Wunused-variable]
   int tot = 0;
       ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 310 ms 15224 KB Output is correct
12 Correct 336 ms 14764 KB Output is correct
13 Correct 354 ms 13984 KB Output is correct
14 Correct 406 ms 14200 KB Output is correct
15 Correct 339 ms 15104 KB Output is correct
16 Correct 412 ms 14328 KB Output is correct
17 Correct 398 ms 14308 KB Output is correct
18 Correct 229 ms 16252 KB Output is correct
19 Correct 310 ms 13172 KB Output is correct
20 Correct 338 ms 14812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 310 ms 15224 KB Output is correct
12 Correct 336 ms 14764 KB Output is correct
13 Correct 354 ms 13984 KB Output is correct
14 Correct 406 ms 14200 KB Output is correct
15 Correct 339 ms 15104 KB Output is correct
16 Correct 412 ms 14328 KB Output is correct
17 Correct 398 ms 14308 KB Output is correct
18 Correct 229 ms 16252 KB Output is correct
19 Correct 310 ms 13172 KB Output is correct
20 Correct 338 ms 14812 KB Output is correct
21 Correct 364 ms 18216 KB Output is correct
22 Correct 398 ms 18316 KB Output is correct
23 Correct 475 ms 17400 KB Output is correct
24 Correct 551 ms 17272 KB Output is correct
25 Correct 388 ms 19192 KB Output is correct
26 Correct 520 ms 17772 KB Output is correct
27 Correct 497 ms 17736 KB Output is correct
28 Correct 247 ms 20216 KB Output is correct
29 Correct 343 ms 16104 KB Output is correct
30 Correct 396 ms 18308 KB Output is correct
31 Correct 464 ms 18296 KB Output is correct
32 Correct 539 ms 18220 KB Output is correct
33 Correct 401 ms 17056 KB Output is correct
34 Correct 509 ms 17200 KB Output is correct
35 Correct 521 ms 17656 KB Output is correct
36 Correct 345 ms 16272 KB Output is correct
37 Correct 372 ms 18228 KB Output is correct
38 Correct 350 ms 16120 KB Output is correct
39 Correct 441 ms 17508 KB Output is correct
40 Correct 532 ms 17212 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 68 ms 16152 KB Output is correct
12 Correct 71 ms 16152 KB Output is correct
13 Correct 90 ms 16024 KB Output is correct
14 Correct 202 ms 16028 KB Output is correct
15 Correct 71 ms 16124 KB Output is correct
16 Correct 124 ms 16024 KB Output is correct
17 Correct 115 ms 16028 KB Output is correct
18 Correct 57 ms 16284 KB Output is correct
19 Correct 67 ms 15896 KB Output is correct
20 Correct 70 ms 16272 KB Output is correct
21 Correct 89 ms 16160 KB Output is correct
22 Correct 127 ms 16152 KB Output is correct
23 Correct 74 ms 16024 KB Output is correct
24 Correct 180 ms 16148 KB Output is correct
25 Correct 115 ms 16024 KB Output is correct
26 Correct 64 ms 16024 KB Output is correct
27 Correct 70 ms 16152 KB Output is correct
28 Correct 67 ms 15896 KB Output is correct
29 Correct 84 ms 16024 KB Output is correct
30 Correct 114 ms 16024 KB Output is correct
31 Correct 76 ms 16024 KB Output is correct
32 Correct 131 ms 16024 KB Output is correct
33 Correct 156 ms 16024 KB Output is correct
34 Correct 64 ms 15900 KB Output is correct
35 Correct 126 ms 16068 KB Output is correct
36 Correct 107 ms 16280 KB Output is correct
37 Correct 104 ms 16068 KB Output is correct
38 Correct 101 ms 16152 KB Output is correct
39 Correct 104 ms 16032 KB Output is correct
40 Correct 103 ms 16124 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 310 ms 15224 KB Output is correct
12 Correct 336 ms 14764 KB Output is correct
13 Correct 354 ms 13984 KB Output is correct
14 Correct 406 ms 14200 KB Output is correct
15 Correct 339 ms 15104 KB Output is correct
16 Correct 412 ms 14328 KB Output is correct
17 Correct 398 ms 14308 KB Output is correct
18 Correct 229 ms 16252 KB Output is correct
19 Correct 310 ms 13172 KB Output is correct
20 Correct 338 ms 14812 KB Output is correct
21 Correct 364 ms 18216 KB Output is correct
22 Correct 398 ms 18316 KB Output is correct
23 Correct 475 ms 17400 KB Output is correct
24 Correct 551 ms 17272 KB Output is correct
25 Correct 388 ms 19192 KB Output is correct
26 Correct 520 ms 17772 KB Output is correct
27 Correct 497 ms 17736 KB Output is correct
28 Correct 247 ms 20216 KB Output is correct
29 Correct 343 ms 16104 KB Output is correct
30 Correct 396 ms 18308 KB Output is correct
31 Correct 464 ms 18296 KB Output is correct
32 Correct 539 ms 18220 KB Output is correct
33 Correct 401 ms 17056 KB Output is correct
34 Correct 509 ms 17200 KB Output is correct
35 Correct 521 ms 17656 KB Output is correct
36 Correct 345 ms 16272 KB Output is correct
37 Correct 372 ms 18228 KB Output is correct
38 Correct 350 ms 16120 KB Output is correct
39 Correct 441 ms 17508 KB Output is correct
40 Correct 532 ms 17212 KB Output is correct
41 Correct 68 ms 16152 KB Output is correct
42 Correct 71 ms 16152 KB Output is correct
43 Correct 90 ms 16024 KB Output is correct
44 Correct 202 ms 16028 KB Output is correct
45 Correct 71 ms 16124 KB Output is correct
46 Correct 124 ms 16024 KB Output is correct
47 Correct 115 ms 16028 KB Output is correct
48 Correct 57 ms 16284 KB Output is correct
49 Correct 67 ms 15896 KB Output is correct
50 Correct 70 ms 16272 KB Output is correct
51 Correct 89 ms 16160 KB Output is correct
52 Correct 127 ms 16152 KB Output is correct
53 Correct 74 ms 16024 KB Output is correct
54 Correct 180 ms 16148 KB Output is correct
55 Correct 115 ms 16024 KB Output is correct
56 Correct 64 ms 16024 KB Output is correct
57 Correct 70 ms 16152 KB Output is correct
58 Correct 67 ms 15896 KB Output is correct
59 Correct 84 ms 16024 KB Output is correct
60 Correct 114 ms 16024 KB Output is correct
61 Correct 76 ms 16024 KB Output is correct
62 Correct 131 ms 16024 KB Output is correct
63 Correct 156 ms 16024 KB Output is correct
64 Correct 64 ms 15900 KB Output is correct
65 Correct 126 ms 16068 KB Output is correct
66 Correct 107 ms 16280 KB Output is correct
67 Correct 104 ms 16068 KB Output is correct
68 Correct 101 ms 16152 KB Output is correct
69 Correct 104 ms 16032 KB Output is correct
70 Correct 103 ms 16124 KB Output is correct
71 Correct 607 ms 40348 KB Output is correct
72 Correct 627 ms 40600 KB Output is correct
73 Correct 952 ms 39068 KB Output is correct
74 Correct 1741 ms 39528 KB Output is correct
75 Correct 619 ms 41416 KB Output is correct
76 Correct 1779 ms 39692 KB Output is correct
77 Correct 1534 ms 39668 KB Output is correct
78 Correct 348 ms 43336 KB Output is correct
79 Correct 546 ms 37332 KB Output is correct
80 Correct 619 ms 40600 KB Output is correct
81 Correct 1025 ms 40532 KB Output is correct
82 Correct 2000 ms 39516 KB Output is correct
83 Correct 659 ms 38560 KB Output is correct
84 Correct 1918 ms 39576 KB Output is correct
85 Correct 1569 ms 39664 KB Output is correct
86 Correct 492 ms 37400 KB Output is correct
87 Correct 610 ms 40344 KB Output is correct
88 Correct 571 ms 37500 KB Output is correct
89 Correct 912 ms 39196 KB Output is correct
90 Correct 1373 ms 39456 KB Output is correct
91 Correct 652 ms 38556 KB Output is correct
92 Correct 1936 ms 39816 KB Output is correct
93 Correct 1513 ms 39704 KB Output is correct
94 Correct 461 ms 37408 KB Output is correct
95 Correct 1246 ms 39616 KB Output is correct
96 Correct 1276 ms 39704 KB Output is correct
97 Correct 1229 ms 39648 KB Output is correct
98 Correct 1224 ms 39732 KB Output is correct
99 Correct 1235 ms 39644 KB Output is correct
100 Correct 1283 ms 39672 KB Output is correct