oj.uz

Submission #130127

# Submission time Handle Problem Language Result Execution time Memory
130127 2019-07-14T04:36:13 Z qkxwsm Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 21880 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;
}

template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}

#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]; //b is for big [superset]
vi freq[3];
int ans;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	readi(N); readi(Q);
	FOR(i, 0, (1 << N))
	{
		char c = getchar();
		arr[i] = c - '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--)
	{
		ans = 0;
		int tot = 0;
		FOR(i, 0, 3) freq[i].clear();
		char c = getchar();
		FOR(i, 0, N)
		{
			c = getchar();
			int want = c - '0';
			if (c == '?') want = 2;
			freq[want].PB(N - 1 - 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];
			}
		}
		printi(ans); putchar('\n');
	}
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 2 ms 376 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 351 ms 15156 KB Output is correct
12 Correct 355 ms 14764 KB Output is correct
13 Correct 347 ms 14048 KB Output is correct
14 Correct 407 ms 14060 KB Output is correct
15 Correct 368 ms 15136 KB Output is correct
16 Correct 401 ms 14304 KB Output is correct
17 Correct 387 ms 14296 KB Output is correct
18 Correct 299 ms 16096 KB Output is correct
19 Correct 275 ms 13048 KB Output is correct
20 Correct 356 ms 14872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 351 ms 15156 KB Output is correct
12 Correct 355 ms 14764 KB Output is correct
13 Correct 347 ms 14048 KB Output is correct
14 Correct 407 ms 14060 KB Output is correct
15 Correct 368 ms 15136 KB Output is correct
16 Correct 401 ms 14304 KB Output is correct
17 Correct 387 ms 14296 KB Output is correct
18 Correct 299 ms 16096 KB Output is correct
19 Correct 275 ms 13048 KB Output is correct
20 Correct 356 ms 14872 KB Output is correct
21 Correct 423 ms 18056 KB Output is correct
22 Correct 443 ms 18372 KB Output is correct
23 Correct 450 ms 17292 KB Output is correct
24 Correct 561 ms 17232 KB Output is correct
25 Correct 474 ms 19144 KB Output is correct
26 Correct 559 ms 17644 KB Output is correct
27 Correct 499 ms 17616 KB Output is correct
28 Correct 374 ms 20340 KB Output is correct
29 Correct 355 ms 16032 KB Output is correct
30 Correct 444 ms 18336 KB Output is correct
31 Correct 488 ms 18164 KB Output is correct
32 Correct 576 ms 18164 KB Output is correct
33 Correct 425 ms 17144 KB Output is correct
34 Correct 521 ms 17164 KB Output is correct
35 Correct 533 ms 17584 KB Output is correct
36 Correct 360 ms 16292 KB Output is correct
37 Correct 429 ms 18088 KB Output is correct
38 Correct 369 ms 16248 KB Output is correct
39 Correct 455 ms 17356 KB Output is correct
40 Correct 555 ms 17156 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 90 ms 14968 KB Output is correct
12 Correct 115 ms 14968 KB Output is correct
13 Correct 101 ms 14940 KB Output is correct
14 Correct 147 ms 15008 KB Output is correct
15 Correct 93 ms 14964 KB Output is correct
16 Correct 139 ms 14976 KB Output is correct
17 Correct 145 ms 14968 KB Output is correct
18 Correct 82 ms 15140 KB Output is correct
19 Correct 83 ms 14840 KB Output is correct
20 Correct 91 ms 15008 KB Output is correct
21 Correct 104 ms 15000 KB Output is correct
22 Correct 132 ms 14840 KB Output is correct
23 Correct 91 ms 14840 KB Output is correct
24 Correct 148 ms 14888 KB Output is correct
25 Correct 126 ms 14892 KB Output is correct
26 Correct 90 ms 14864 KB Output is correct
27 Correct 88 ms 15044 KB Output is correct
28 Correct 91 ms 14812 KB Output is correct
29 Correct 109 ms 14864 KB Output is correct
30 Correct 120 ms 14864 KB Output is correct
31 Correct 87 ms 14840 KB Output is correct
32 Correct 192 ms 14856 KB Output is correct
33 Correct 144 ms 14968 KB Output is correct
34 Correct 88 ms 14840 KB Output is correct
35 Correct 119 ms 14968 KB Output is correct
36 Correct 116 ms 14968 KB Output is correct
37 Correct 117 ms 14840 KB Output is correct
38 Correct 117 ms 14840 KB Output is correct
39 Correct 133 ms 15068 KB Output is correct
40 Correct 130 ms 14984 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 351 ms 15156 KB Output is correct
12 Correct 355 ms 14764 KB Output is correct
13 Correct 347 ms 14048 KB Output is correct
14 Correct 407 ms 14060 KB Output is correct
15 Correct 368 ms 15136 KB Output is correct
16 Correct 401 ms 14304 KB Output is correct
17 Correct 387 ms 14296 KB Output is correct
18 Correct 299 ms 16096 KB Output is correct
19 Correct 275 ms 13048 KB Output is correct
20 Correct 356 ms 14872 KB Output is correct
21 Correct 423 ms 18056 KB Output is correct
22 Correct 443 ms 18372 KB Output is correct
23 Correct 450 ms 17292 KB Output is correct
24 Correct 561 ms 17232 KB Output is correct
25 Correct 474 ms 19144 KB Output is correct
26 Correct 559 ms 17644 KB Output is correct
27 Correct 499 ms 17616 KB Output is correct
28 Correct 374 ms 20340 KB Output is correct
29 Correct 355 ms 16032 KB Output is correct
30 Correct 444 ms 18336 KB Output is correct
31 Correct 488 ms 18164 KB Output is correct
32 Correct 576 ms 18164 KB Output is correct
33 Correct 425 ms 17144 KB Output is correct
34 Correct 521 ms 17164 KB Output is correct
35 Correct 533 ms 17584 KB Output is correct
36 Correct 360 ms 16292 KB Output is correct
37 Correct 429 ms 18088 KB Output is correct
38 Correct 369 ms 16248 KB Output is correct
39 Correct 455 ms 17356 KB Output is correct
40 Correct 555 ms 17156 KB Output is correct
41 Correct 90 ms 14968 KB Output is correct
42 Correct 115 ms 14968 KB Output is correct
43 Correct 101 ms 14940 KB Output is correct
44 Correct 147 ms 15008 KB Output is correct
45 Correct 93 ms 14964 KB Output is correct
46 Correct 139 ms 14976 KB Output is correct
47 Correct 145 ms 14968 KB Output is correct
48 Correct 82 ms 15140 KB Output is correct
49 Correct 83 ms 14840 KB Output is correct
50 Correct 91 ms 15008 KB Output is correct
51 Correct 104 ms 15000 KB Output is correct
52 Correct 132 ms 14840 KB Output is correct
53 Correct 91 ms 14840 KB Output is correct
54 Correct 148 ms 14888 KB Output is correct
55 Correct 126 ms 14892 KB Output is correct
56 Correct 90 ms 14864 KB Output is correct
57 Correct 88 ms 15044 KB Output is correct
58 Correct 91 ms 14812 KB Output is correct
59 Correct 109 ms 14864 KB Output is correct
60 Correct 120 ms 14864 KB Output is correct
61 Correct 87 ms 14840 KB Output is correct
62 Correct 192 ms 14856 KB Output is correct
63 Correct 144 ms 14968 KB Output is correct
64 Correct 88 ms 14840 KB Output is correct
65 Correct 119 ms 14968 KB Output is correct
66 Correct 116 ms 14968 KB Output is correct
67 Correct 117 ms 14840 KB Output is correct
68 Correct 117 ms 14840 KB Output is correct
69 Correct 133 ms 15068 KB Output is correct
70 Correct 130 ms 14984 KB Output is correct
71 Correct 788 ms 18848 KB Output is correct
72 Correct 847 ms 19024 KB Output is correct
73 Correct 986 ms 17688 KB Output is correct
74 Correct 1837 ms 17828 KB Output is correct
75 Correct 806 ms 20072 KB Output is correct
76 Correct 1786 ms 18248 KB Output is correct
77 Correct 1547 ms 18216 KB Output is correct
78 Correct 610 ms 21880 KB Output is correct
79 Correct 611 ms 16032 KB Output is correct
80 Correct 771 ms 19132 KB Output is correct
81 Correct 1116 ms 18992 KB Output is correct
82 Correct 1916 ms 17912 KB Output is correct
83 Correct 730 ms 17188 KB Output is correct
84 Correct 2000 ms 17908 KB Output is correct
85 Correct 1579 ms 18220 KB Output is correct
86 Correct 580 ms 16024 KB Output is correct
87 Correct 784 ms 19004 KB Output is correct
88 Correct 677 ms 15864 KB Output is correct
89 Correct 1022 ms 17656 KB Output is correct
90 Correct 1476 ms 18004 KB Output is correct
91 Correct 755 ms 16996 KB Output is correct
92 Execution timed out 2008 ms 18384 KB Time limit exceeded
93 Halted 0 ms 0 KB -