oj.uz

Submission #315414

# Submission time Handle Problem Language Result Execution time Memory
315414 2020-10-22T21:18:10 Z aZvezda Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 2000 ms 47416 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 = 600000; 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];
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 26 ms 33280 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33400 KB Output is correct
4 Correct 26 ms 33280 KB Output is correct
5 Correct 27 ms 33280 KB Output is correct
6 Correct 26 ms 33280 KB Output is correct
7 Correct 26 ms 33280 KB Output is correct
8 Correct 26 ms 33280 KB Output is correct
9 Correct 26 ms 33280 KB Output is correct
10 Correct 26 ms 33280 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 33280 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33400 KB Output is correct
4 Correct 26 ms 33280 KB Output is correct
5 Correct 27 ms 33280 KB Output is correct
6 Correct 26 ms 33280 KB Output is correct
7 Correct 26 ms 33280 KB Output is correct
8 Correct 26 ms 33280 KB Output is correct
9 Correct 26 ms 33280 KB Output is correct
10 Correct 26 ms 33280 KB Output is correct
11 Correct 491 ms 46876 KB Output is correct
12 Correct 495 ms 47000 KB Output is correct
13 Correct 486 ms 46108 KB Output is correct
14 Correct 508 ms 46108 KB Output is correct
15 Correct 512 ms 46492 KB Output is correct
16 Correct 525 ms 46092 KB Output is correct
17 Correct 509 ms 46104 KB Output is correct
18 Correct 533 ms 47256 KB Output is correct
19 Correct 463 ms 45976 KB Output is correct
20 Correct 489 ms 47128 KB Output is correct
21 Correct 507 ms 46104 KB Output is correct
22 Correct 506 ms 46104 KB Output is correct
23 Correct 431 ms 46232 KB Output is correct
24 Correct 506 ms 45976 KB Output is correct
25 Correct 510 ms 45976 KB Output is correct
26 Correct 357 ms 46744 KB Output is correct
27 Correct 497 ms 46876 KB Output is correct
28 Correct 466 ms 45848 KB Output is correct
29 Correct 483 ms 45976 KB Output is correct
30 Correct 504 ms 45976 KB Output is correct
31 Correct 437 ms 46104 KB Output is correct
32 Correct 508 ms 45976 KB Output is correct
33 Correct 510 ms 45976 KB Output is correct
34 Correct 356 ms 46744 KB Output is correct
35 Correct 506 ms 46104 KB Output is correct
36 Correct 503 ms 46104 KB Output is correct
37 Correct 504 ms 46104 KB Output is correct
38 Correct 506 ms 46100 KB Output is correct
39 Correct 515 ms 46080 KB Output is correct
40 Correct 508 ms 46104 KB Output is correct

Subtask #5
0 / 25.0

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