oj.uz

Submission #315415

# Submission time Handle Problem Language Result Execution time Memory
315415 2020-10-22T21:18:34 Z aZvezda Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 1616 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const ll MAX_N = 1 << 20;
const ll MAX_RIGHT = 4800000; ll MAX_LEFT = 6;
ll pow3[50];
int dp[MAX_RIGHT];
int price[MAX_N];
string queries[MAX_N];
int ans[MAX_N];
int n, q;
int sum[MAX_RIGHT], first2[MAX_RIGHT];
int rightPart[MAX_N];

void prec() {
	for(int i = 0; i < q; i ++) {
		ll currMask = 0;
		for(ll j = n - 1; j >= MAX_LEFT; j --) {
			currMask *= 3;
			currMask += (ll)(queries[i][j] - '0');
		}
		rightPart[i] = currMask;
	}

	ll triBits = n - MAX_LEFT;
	for(ll i = 0; i < pow3[triBits]; i ++) {
		bool flag = false;
		for(ll j = triBits - 1; j >= 0; j --) {
			if((i / pow3[j]) % 3 == 2) {
				first2[i] = j;
				flag = true;
				break;
			}
		}
		if(!flag) {
			ll currMask = 0;
			for(ll j = triBits - 1; j >= 0; j --) {
				currMask += ((i / pow3[j]) % 3) * (1 << (j + MAX_LEFT));
			}
			sum[i] = currMask;
			first2[i] = -1;
		}
	}
}

void getAns(ll mask) {
	vector<ll> indices;
	for(ll i = 0; i < q; i ++) {
		for(ll j = 0; j < MAX_LEFT; j ++) {
			if(mask & (1 << j)) {
				if(queries[i][j] == '0') {
					break;
				}
			} else {
				if(queries[i][j] == '1') {
					break;
				}				
			}
			if(j == MAX_LEFT - 1) {
				indices.push_back(i);
			}
		}
	}
	
	ll triBits = n - MAX_LEFT;
	for(ll i = 0; i < pow3[triBits]; i ++) {
		if(first2[i] != -1) {
			int j = first2[i];		
			dp[i] = dp[i - pow3[j]] + dp[i - 2 * pow3[j]]; 
		} else {
			ll currMask = mask + sum[i];
			dp[i] = price[currMask];			
		}
	}
	
	for(auto it : indices) {
		ans[it] += dp[rightPart[it]];
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	pow3[0] = 1;
	for(ll i = 1; i < 50; i ++) {
		pow3[i] = pow3[i - 1] * 3ll;
	}
	cin >> n >> q;
	chkmin(MAX_LEFT, n);
	string in;
	cin >> in;
	for(ll i = 0; i < (1 << n); i ++) {
		price[i] = in[i] - '0';
	}
	for(ll i = 0; i < q; i ++) {
		cin >> queries[i];
		reverse(queries[i].begin(), queries[i].end());
		for(auto &it : queries[i]) {
			if(it == '?') {
				it = '2';
			}
		}
	}
		
	prec();
	for(ll mask = 0; mask < (1 << MAX_LEFT); mask ++) {
		getAns(mask);
	}
	for(ll i = 0; i < q; i ++) {
		cout << ans[i] << endl;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33280 KB Output is correct
3 Correct 23 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 24 ms 33276 KB Output is correct
7 Correct 23 ms 33280 KB Output is correct
8 Correct 23 ms 33280 KB Output is correct
9 Correct 23 ms 33152 KB Output is correct
10 Correct 23 ms 33280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33280 KB Output is correct
3 Correct 23 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 24 ms 33276 KB Output is correct
7 Correct 23 ms 33280 KB Output is correct
8 Correct 23 ms 33280 KB Output is correct
9 Correct 23 ms 33152 KB Output is correct
10 Correct 23 ms 33280 KB Output is correct
11 Correct 1164 ms 53640 KB Output is correct
12 Correct 1223 ms 53168 KB Output is correct
13 Correct 1159 ms 46428 KB Output is correct
14 Correct 1280 ms 45832 KB Output is correct
15 Correct 1363 ms 45924 KB Output is correct
16 Correct 1319 ms 45428 KB Output is correct
17 Correct 1331 ms 44780 KB Output is correct
18 Correct 1601 ms 57776 KB Output is correct
19 Correct 1063 ms 43760 KB Output is correct
20 Correct 1229 ms 53856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33280 KB Output is correct
3 Correct 23 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 24 ms 33276 KB Output is correct
7 Correct 23 ms 33280 KB Output is correct
8 Correct 23 ms 33280 KB Output is correct
9 Correct 23 ms 33152 KB Output is correct
10 Correct 23 ms 33280 KB Output is correct
11 Correct 1164 ms 53640 KB Output is correct
12 Correct 1223 ms 53168 KB Output is correct
13 Correct 1159 ms 46428 KB Output is correct
14 Correct 1280 ms 45832 KB Output is correct
15 Correct 1363 ms 45924 KB Output is correct
16 Correct 1319 ms 45428 KB Output is correct
17 Correct 1331 ms 44780 KB Output is correct
18 Correct 1601 ms 57776 KB Output is correct
19 Correct 1063 ms 43760 KB Output is correct
20 Correct 1229 ms 53856 KB Output is correct
21 Correct 1291 ms 59144 KB Output is correct
22 Correct 1251 ms 53688 KB Output is correct
23 Correct 1229 ms 46680 KB Output is correct
24 Correct 1306 ms 45816 KB Output is correct
25 Correct 1384 ms 46736 KB Output is correct
26 Correct 1356 ms 45956 KB Output is correct
27 Correct 1352 ms 45452 KB Output is correct
28 Correct 1616 ms 59340 KB Output is correct
29 Correct 1074 ms 57184 KB Output is correct
30 Correct 1259 ms 65536 KB Output is correct
31 Correct 1377 ms 61272 KB Output is correct
32 Correct 1359 ms 59972 KB Output is correct
33 Correct 1002 ms 58856 KB Output is correct
34 Correct 1336 ms 58092 KB Output is correct
35 Correct 1351 ms 58660 KB Output is correct
36 Correct 467 ms 63048 KB Output is correct
37 Correct 1154 ms 65536 KB Output is correct
38 Correct 1113 ms 57032 KB Output is correct
39 Correct 1252 ms 58304 KB Output is correct
40 Correct 1317 ms 58740 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33280 KB Output is correct
3 Correct 23 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 24 ms 33276 KB Output is correct
7 Correct 23 ms 33280 KB Output is correct
8 Correct 23 ms 33280 KB Output is correct
9 Correct 23 ms 33152 KB Output is correct
10 Correct 23 ms 33280 KB Output is correct
11 Runtime error 154 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33280 KB Output is correct
2 Correct 23 ms 33280 KB Output is correct
3 Correct 23 ms 33280 KB Output is correct
4 Correct 23 ms 33280 KB Output is correct
5 Correct 23 ms 33280 KB Output is correct
6 Correct 24 ms 33276 KB Output is correct
7 Correct 23 ms 33280 KB Output is correct
8 Correct 23 ms 33280 KB Output is correct
9 Correct 23 ms 33152 KB Output is correct
10 Correct 23 ms 33280 KB Output is correct
11 Correct 1164 ms 53640 KB Output is correct
12 Correct 1223 ms 53168 KB Output is correct
13 Correct 1159 ms 46428 KB Output is correct
14 Correct 1280 ms 45832 KB Output is correct
15 Correct 1363 ms 45924 KB Output is correct
16 Correct 1319 ms 45428 KB Output is correct
17 Correct 1331 ms 44780 KB Output is correct
18 Correct 1601 ms 57776 KB Output is correct
19 Correct 1063 ms 43760 KB Output is correct
20 Correct 1229 ms 53856 KB Output is correct
21 Correct 1291 ms 59144 KB Output is correct
22 Correct 1251 ms 53688 KB Output is correct
23 Correct 1229 ms 46680 KB Output is correct
24 Correct 1306 ms 45816 KB Output is correct
25 Correct 1384 ms 46736 KB Output is correct
26 Correct 1356 ms 45956 KB Output is correct
27 Correct 1352 ms 45452 KB Output is correct
28 Correct 1616 ms 59340 KB Output is correct
29 Correct 1074 ms 57184 KB Output is correct
30 Correct 1259 ms 65536 KB Output is correct
31 Correct 1377 ms 61272 KB Output is correct
32 Correct 1359 ms 59972 KB Output is correct
33 Correct 1002 ms 58856 KB Output is correct
34 Correct 1336 ms 58092 KB Output is correct
35 Correct 1351 ms 58660 KB Output is correct
36 Correct 467 ms 63048 KB Output is correct
37 Correct 1154 ms 65536 KB Output is correct
38 Correct 1113 ms 57032 KB Output is correct
39 Correct 1252 ms 58304 KB Output is correct
40 Correct 1317 ms 58740 KB Output is correct
41 Runtime error 154 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -