oj.uz

Submission #213501

# Submission time Handle Problem Language Result Execution time Memory
213501 2020-03-26T02:46:10 Z AQT Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 2000 ms 15096 KB 
#include <bits/stdc++.h>

using namespace std;

int N, L, Q;
int arr[1<<20];
int pre[2][1<<20];
int cnt[3];
vector<int> lst;

void rec(int n, vector<int> v){
	if(n == -1){
		int msk = 0;
		for(int m = 0; m<L; m++){
			msk *= 2;
			msk += v[m];
		}
		lst.emplace_back(msk);
		return;
	}
	//long long ret = 0;
	if(v[n] == 2){
		v[n] = 0;
		rec(n-1, v);
		v[n] = 1;
		rec(n-1, v);
		v[n] = 2;
	}
	else{
		rec(n-1, v);
	}
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> L >> Q;
	N = 1<<L;
	for(int m = 0; m<N; m++){
		char c;
		cin >> c;
		arr[m] = c-'0';
		pre[0][m] = arr[m];
	}
	for(int m = 0; m<N; m++){
		pre[1][m] = arr[m^(N-1)];
	}
	for(int d = 0; d<L; d++){
		for(int m = N-1; m>=0; m--){
			if((1<<d)&m){
				pre[0][m] += pre[0][m^(1<<d)];
				pre[1][m] += pre[1][m^(1<<d)];
			}			
		}
	}
	/*
	for(int m = 0; m<N; m++){
		//cout << m << " " << pre[0][m] << "\n";
	}
	*/
	while(Q--){
		vector<int> v;
		cnt[0] = cnt[1] = cnt[2] = 0;
		for(int k = 0; k<L; k++){
			char c;
			cin >> c;
			if(c == '?'){
				v.emplace_back(2);
			}
			else{
				v.emplace_back(c-'0');
			}
			cnt[v.back()]++;
		}
		long long ret = 0;
		if(min({cnt[0], cnt[1], cnt[2]}) == cnt[2]){
			rec(L-1, v);
			for(int m : lst){
				ret += arr[m];
			}
		}
		else if(min({cnt[0], cnt[1], cnt[2]}) == cnt[1]){
			for(int k = 0; k<L; k++){
				if(v[k] == 2){
					v[k] = 1;
				}
				else if(v[k] == 1){
					v[k] = 2;
				}
				else{
					v[k] = 0;
				}
			}			
			rec(L-1, v);
			for(int m : lst){
				int c = __builtin_popcount(m)&1;
				c *= 2;
				c--;
				ret += pre[0][m]*c;
			}
		}
		else{
			for(int k = 0; k<L; k++){
				if(v[k] == 2){
					v[k] = 1;
				}
				else if(v[k] == 1){
					v[k] = 0;
				}
				else{
					v[k] = 2;
				}
			}
			rec(L-1, v);			
			for(int m : lst){
				int c = __builtin_popcount(m)&1;
				c *= 2;
				c--;
				ret += pre[1][m]*c;
			}
		}
		cout << abs(ret) << "\n";
		lst.clear();
	}
}

/*
#include <bits/stdc++.h>

using namespace std;

int N, L, Q, T;
int arr[1<<20];
int dp[60000];
vector<char> ternary[60000];
int pows[20];
int pre[1000005];
vector<char> qu[1000005];
int ans[1000005];

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> L >> Q;
	N = 1<<L;
	for(int m = 0; m<N; m++){
		char c;
		cin >> c;
		arr[m] = c-'0';
	}
	int H = L/2;
	T = 1;
	pows[0] = 1;
	for(int k = 0; k<H; k++){
		T *= 3;
		pows[k+1] = pows[k] * 3;
	}
	for(int m = 0; m<T; m++){
		int temp = m;
		for(int k = 0; k<H; k++){
			ternary[m].emplace_back(temp%3);
			temp /= 3;
		}
	}
	for(int q = 1; q<=Q; q++){
		int t = 0;
		for(int i = 0; i<L; i++){
			char c;
			cin >> c;
			if(c == '?'){
				qu[q].emplace_back(2);
			}
			else{
				qu[q].emplace_back(c-'0');
			}
		}
		for(int k = 0; k<H; k++){
			t *= 3;
			t += qu[q][k];
		}
		reverse(qu[q].begin(), qu[q].end());
		pre[q] = t;
	}
	for(int m = 0; m<1<<(L-H); m++){
		fill(dp, dp+T, 0);
		for(int t = 0; t<T; t++){
			bool has2 = 0;
			int temp = 0;
			for(int h = 0; h<H; h++){
				if(ternary[t][h] == 2){
					has2 = 1;
					dp[t] = dp[t-pows[h]] + dp[t-pows[h]*2];
					break;
				}
				temp += (1<<h)*ternary[t][h];
			}
			if(!has2){
				dp[t] = arr[(temp<<(L-H)) + m];
			}
		}
		for(int q = 1; q<=Q; q++){
			bool good = 1;
			for(int b = 0; b<L-H; b++){
				if(qu[q][b] == 2 || qu[q][b] == ((m>>b)&1)){
					
				}
				else{
					good = 0;
					break;
				}
			}
			if(good){
				ans[q] += dp[pre[q]];
			}
		}
	}
	for(int q = 1; q<=Q; q++){
		cout << ans[q] << "\n";
	}
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 1110 ms 4856 KB Output is correct
12 Correct 1134 ms 4856 KB Output is correct
13 Correct 1560 ms 4088 KB Output is correct
14 Execution timed out 2099 ms 3832 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 1110 ms 4856 KB Output is correct
12 Correct 1134 ms 4856 KB Output is correct
13 Correct 1560 ms 4088 KB Output is correct
14 Execution timed out 2099 ms 3832 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 151 ms 12924 KB Output is correct
12 Correct 152 ms 12920 KB Output is correct
13 Correct 379 ms 12920 KB Output is correct
14 Correct 955 ms 12920 KB Output is correct
15 Correct 239 ms 13048 KB Output is correct
16 Correct 746 ms 14968 KB Output is correct
17 Correct 562 ms 14968 KB Output is correct
18 Correct 137 ms 15096 KB Output is correct
19 Correct 146 ms 14840 KB Output is correct
20 Correct 158 ms 14968 KB Output is correct
21 Correct 410 ms 14968 KB Output is correct
22 Correct 971 ms 14968 KB Output is correct
23 Correct 232 ms 14840 KB Output is correct
24 Correct 733 ms 14968 KB Output is correct
25 Correct 566 ms 14968 KB Output is correct
26 Correct 140 ms 14840 KB Output is correct
27 Correct 155 ms 14968 KB Output is correct
28 Correct 142 ms 14840 KB Output is correct
29 Correct 382 ms 14968 KB Output is correct
30 Correct 933 ms 14968 KB Output is correct
31 Correct 228 ms 14840 KB Output is correct
32 Correct 759 ms 14968 KB Output is correct
33 Correct 574 ms 14968 KB Output is correct
34 Correct 137 ms 14840 KB Output is correct
35 Correct 435 ms 14968 KB Output is correct
36 Correct 420 ms 14968 KB Output is correct
37 Correct 439 ms 14968 KB Output is correct
38 Correct 415 ms 14972 KB Output is correct
39 Correct 423 ms 14968 KB Output is correct
40 Correct 424 ms 14968 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 1110 ms 4856 KB Output is correct
12 Correct 1134 ms 4856 KB Output is correct
13 Correct 1560 ms 4088 KB Output is correct
14 Execution timed out 2099 ms 3832 KB Time limit exceeded
15 Halted 0 ms 0 KB -