oj.uz

Submission #1115162

# Submission time Handle Problem Language Result Execution time Memory
1115162 2024-11-20T07:27:21 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 19348 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
 
string s;
int n, l, q;
const int p3[] = {1,3,9,27,81,243,729,729*3,729*9,729*27,729*81,729*243,729*729};
const int B1 = 3;
const int B2 = 20-B1;
const int N = p3[B1];
int score[N+2][(1<<B2)+2];
 
int calc(string lol){
	int p = 1, ans = 0, xd;
	for(int i = 0; i < B1; i++){
		if(lol[i]=='?') xd=2;
		else xd = lol[i]-'0';
		ans+=xd*p, p*=3;
	}
	return ans;
}
 
int calc(int lol){
	int p = 1, ans = 0;
	while(lol){
		int r = lol%2; lol/=2;
		ans+=r*p; p*=3;
	}
	return ans;
}
 
int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> l >> q >> s; n = (1<<l);
	if(l<B1){
		for(int _ = 0; _ < q; _++){
			string t; cin >> t; 
			reverse(all(t));
			int cnt = 0;
			for(int i = 0; i < n; i++){
				int ok = 1;
				for(int j = 0; j < l; j++) 
					ok&=(t[j]=='?' or (t[j]-'0')==(i>>j&1));
				cnt+=ok*(s[i]-'0');
			}
			cout << cnt << "\n";
		}
		return 0;
	}
	l-=B1;
	for(int mask = 0; mask < n; mask++){
		int mask1 = calc(mask&((1<<B1)-1));
		int mask2 = mask>>B1;
		int sc = s[mask]-'0';
		score[mask1][mask2]+=sc;
	}
	for(int mask = 0; mask < (1<<(B1*2)); mask++){
		string t = "", t2 = "";
		for(int i = 0; i < B1*2; i+=2){
			int cur = mask>>i&1;
			t+=(char)(cur+'0');
			if(mask>>(i+1)&1) cur=2;
			t2+=(char)(cur+'0');
		}
		int mask1 = calc(t);
		int mask2 = calc(t2);
		if(t==t2) continue;
		for(int i = 0; i < (1<<l); i++)
			score[mask2][i]+=score[mask1][i];
	}
	for(int _ = 0; _ < q; _++){
		string t; cin >> t; reverse(all(t));
		int x = calc(t.substr(0,B1));
		t = t.substr(B1);
		int cnt = 0, ans = 0, xd2 = 0; 
		vector<int> pos, pos2; 
		pos.clear(); pos2.clear();
		for(int i = 0; i < sz(t); i++){
			if(t[i]=='?') pos.pb(i),cnt++;
			else{
				pos2.pb(i);
				if(t[i]=='1') xd2+=1<<i;
			}
		}
		if(cnt*2<=B2 or 1){
			for(int mask = 0; mask < (1<<cnt); mask++){
				int xd = 0;
				for(int i = 0; i < cnt; i++)
					if(mask>>i&1) xd+=1<<pos[i];
				ans+=score[x][xd+xd2];
			}
		}
		else{
			cnt = sz(pos2);
			for(int mask = 0; mask < (1<<cnt); mask++){
				int num = __builtin_popcount(mask), xd=0;
				for(int i = 0; i < cnt; i++)
					if(mask>>i&1) xd+=(1<<pos2[i])*(t[pos2[i]]=='0');
				ans+=(num%2?-1:1)*score[x][xd];
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8700 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8736 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8696 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 384 ms 12620 KB Output is correct
12 Correct 416 ms 14880 KB Output is correct
13 Correct 300 ms 11504 KB Output is correct
14 Correct 297 ms 12108 KB Output is correct
15 Correct 457 ms 12556 KB Output is correct
16 Correct 314 ms 11848 KB Output is correct
17 Correct 325 ms 12356 KB Output is correct
18 Correct 1239 ms 13916 KB Output is correct
19 Correct 277 ms 10568 KB Output is correct
20 Correct 395 ms 12360 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8700 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8736 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8696 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 384 ms 12620 KB Output is correct
12 Correct 416 ms 14880 KB Output is correct
13 Correct 300 ms 11504 KB Output is correct
14 Correct 297 ms 12108 KB Output is correct
15 Correct 457 ms 12556 KB Output is correct
16 Correct 314 ms 11848 KB Output is correct
17 Correct 325 ms 12356 KB Output is correct
18 Correct 1239 ms 13916 KB Output is correct
19 Correct 277 ms 10568 KB Output is correct
20 Correct 395 ms 12360 KB Output is correct
21 Correct 704 ms 12616 KB Output is correct
22 Correct 860 ms 13960 KB Output is correct
23 Correct 399 ms 15528 KB Output is correct
24 Correct 407 ms 11592 KB Output is correct
25 Correct 1008 ms 13776 KB Output is correct
26 Correct 493 ms 12256 KB Output is correct
27 Correct 479 ms 12360 KB Output is correct
28 Execution timed out 2054 ms 11756 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8700 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8736 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8696 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 249 ms 17204 KB Output is correct
12 Correct 1945 ms 19348 KB Output is correct
13 Correct 65 ms 17308 KB Output is correct
14 Correct 87 ms 19176 KB Output is correct
15 Execution timed out 2047 ms 18664 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8700 KB Output is correct
2 Correct 2 ms 8528 KB Output is correct
3 Correct 2 ms 8528 KB Output is correct
4 Correct 2 ms 8736 KB Output is correct
5 Correct 2 ms 8528 KB Output is correct
6 Correct 2 ms 8528 KB Output is correct
7 Correct 2 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8696 KB Output is correct
10 Correct 2 ms 8528 KB Output is correct
11 Correct 384 ms 12620 KB Output is correct
12 Correct 416 ms 14880 KB Output is correct
13 Correct 300 ms 11504 KB Output is correct
14 Correct 297 ms 12108 KB Output is correct
15 Correct 457 ms 12556 KB Output is correct
16 Correct 314 ms 11848 KB Output is correct
17 Correct 325 ms 12356 KB Output is correct
18 Correct 1239 ms 13916 KB Output is correct
19 Correct 277 ms 10568 KB Output is correct
20 Correct 395 ms 12360 KB Output is correct
21 Correct 704 ms 12616 KB Output is correct
22 Correct 860 ms 13960 KB Output is correct
23 Correct 399 ms 15528 KB Output is correct
24 Correct 407 ms 11592 KB Output is correct
25 Correct 1008 ms 13776 KB Output is correct
26 Correct 493 ms 12256 KB Output is correct
27 Correct 479 ms 12360 KB Output is correct
28 Execution timed out 2054 ms 11756 KB Time limit exceeded
29 Halted 0 ms 0 KB -