oj.uz

Submission #315408

# Submission time Handle Problem Language Result Execution time Memory
315408 2020-10-22T21:11:56 Z aZvezda Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 2000 ms 48792 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 = 1600000; ll MAX_LEFT = 8;
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];

void prec() {
	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) {
		ll currMask = 0;
		for(ll j = n - 1; j >= MAX_LEFT; j --) {
			currMask *= 3;
			currMask += (ll)(queries[it][j] - '0');
		}
		ans[it] += dp[currMask];
	}
}

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 27 ms 33280 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 28 ms 33152 KB Output is correct
5 Correct 27 ms 33152 KB Output is correct
6 Correct 27 ms 33152 KB Output is correct
7 Correct 27 ms 33152 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 26 ms 33152 KB Output is correct
10 Correct 26 ms 33272 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 28 ms 33152 KB Output is correct
5 Correct 27 ms 33152 KB Output is correct
6 Correct 27 ms 33152 KB Output is correct
7 Correct 27 ms 33152 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 26 ms 33152 KB Output is correct
10 Correct 26 ms 33272 KB Output is correct
11 Execution timed out 2074 ms 41200 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 28 ms 33152 KB Output is correct
5 Correct 27 ms 33152 KB Output is correct
6 Correct 27 ms 33152 KB Output is correct
7 Correct 27 ms 33152 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 26 ms 33152 KB Output is correct
10 Correct 26 ms 33272 KB Output is correct
11 Execution timed out 2074 ms 41200 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 28 ms 33152 KB Output is correct
5 Correct 27 ms 33152 KB Output is correct
6 Correct 27 ms 33152 KB Output is correct
7 Correct 27 ms 33152 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 26 ms 33152 KB Output is correct
10 Correct 26 ms 33272 KB Output is correct
11 Correct 568 ms 48536 KB Output is correct
12 Correct 584 ms 48540 KB Output is correct
13 Correct 526 ms 47768 KB Output is correct
14 Correct 565 ms 47640 KB Output is correct
15 Correct 663 ms 48024 KB Output is correct
16 Correct 570 ms 47644 KB Output is correct
17 Correct 570 ms 47640 KB Output is correct
18 Correct 703 ms 48792 KB Output is correct
19 Correct 482 ms 47512 KB Output is correct
20 Correct 584 ms 48684 KB Output is correct
21 Correct 619 ms 47896 KB Output is correct
22 Correct 562 ms 47768 KB Output is correct
23 Correct 458 ms 47772 KB Output is correct
24 Correct 558 ms 47768 KB Output is correct
25 Correct 567 ms 47644 KB Output is correct
26 Correct 353 ms 48408 KB Output is correct
27 Correct 571 ms 48664 KB Output is correct
28 Correct 488 ms 47516 KB Output is correct
29 Correct 528 ms 47640 KB Output is correct
30 Correct 554 ms 47640 KB Output is correct
31 Correct 465 ms 47768 KB Output is correct
32 Correct 568 ms 47640 KB Output is correct
33 Correct 562 ms 47768 KB Output is correct
34 Correct 360 ms 48408 KB Output is correct
35 Correct 605 ms 47896 KB Output is correct
36 Correct 601 ms 47768 KB Output is correct
37 Correct 596 ms 47900 KB Output is correct
38 Correct 613 ms 47772 KB Output is correct
39 Correct 609 ms 47896 KB Output is correct
40 Correct 617 ms 47944 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 26 ms 33272 KB Output is correct
3 Correct 26 ms 33152 KB Output is correct
4 Correct 28 ms 33152 KB Output is correct
5 Correct 27 ms 33152 KB Output is correct
6 Correct 27 ms 33152 KB Output is correct
7 Correct 27 ms 33152 KB Output is correct
8 Correct 28 ms 33280 KB Output is correct
9 Correct 26 ms 33152 KB Output is correct
10 Correct 26 ms 33272 KB Output is correct
11 Execution timed out 2074 ms 41200 KB Time limit exceeded
12 Halted 0 ms 0 KB -