oj.uz

Submission #1115149

# Submission time Handle Problem Language Result Execution time Memory
1115149 2024-11-20T07:12:00 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 1609 ms 49476 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};
const int B1 = 6;
const int B2 = 20-B1;
const int N = p3[B1];
int score[N][1<<B2];
 
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){
			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 5 ms 30288 KB Output is correct
2 Correct 5 ms 30288 KB Output is correct
3 Correct 5 ms 30456 KB Output is correct
4 Correct 5 ms 30288 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30288 KB Output is correct
7 Correct 5 ms 30288 KB Output is correct
8 Correct 4 ms 30288 KB Output is correct
9 Correct 5 ms 30288 KB Output is correct
10 Correct 5 ms 30288 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30288 KB Output is correct
2 Correct 5 ms 30288 KB Output is correct
3 Correct 5 ms 30456 KB Output is correct
4 Correct 5 ms 30288 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30288 KB Output is correct
7 Correct 5 ms 30288 KB Output is correct
8 Correct 4 ms 30288 KB Output is correct
9 Correct 5 ms 30288 KB Output is correct
10 Correct 5 ms 30288 KB Output is correct
11 Correct 251 ms 34312 KB Output is correct
12 Correct 227 ms 33864 KB Output is correct
13 Correct 222 ms 33096 KB Output is correct
14 Correct 224 ms 33352 KB Output is correct
15 Correct 238 ms 34588 KB Output is correct
16 Correct 249 ms 33328 KB Output is correct
17 Correct 257 ms 33352 KB Output is correct
18 Correct 279 ms 35172 KB Output is correct
19 Correct 210 ms 32188 KB Output is correct
20 Correct 261 ms 33804 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30288 KB Output is correct
2 Correct 5 ms 30288 KB Output is correct
3 Correct 5 ms 30456 KB Output is correct
4 Correct 5 ms 30288 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30288 KB Output is correct
7 Correct 5 ms 30288 KB Output is correct
8 Correct 4 ms 30288 KB Output is correct
9 Correct 5 ms 30288 KB Output is correct
10 Correct 5 ms 30288 KB Output is correct
11 Correct 251 ms 34312 KB Output is correct
12 Correct 227 ms 33864 KB Output is correct
13 Correct 222 ms 33096 KB Output is correct
14 Correct 224 ms 33352 KB Output is correct
15 Correct 238 ms 34588 KB Output is correct
16 Correct 249 ms 33328 KB Output is correct
17 Correct 257 ms 33352 KB Output is correct
18 Correct 279 ms 35172 KB Output is correct
19 Correct 210 ms 32188 KB Output is correct
20 Correct 261 ms 33804 KB Output is correct
21 Correct 414 ms 34376 KB Output is correct
22 Correct 407 ms 34460 KB Output is correct
23 Correct 341 ms 47100 KB Output is correct
24 Correct 346 ms 40512 KB Output is correct
25 Correct 468 ms 42036 KB Output is correct
26 Correct 366 ms 44616 KB Output is correct
27 Correct 335 ms 33784 KB Output is correct
28 Correct 1609 ms 40116 KB Output is correct
29 Correct 267 ms 38728 KB Output is correct
30 Correct 400 ms 41032 KB Output is correct
31 Correct 394 ms 41356 KB Output is correct
32 Correct 387 ms 34380 KB Output is correct
33 Correct 293 ms 37016 KB Output is correct
34 Correct 351 ms 43392 KB Output is correct
35 Correct 380 ms 47504 KB Output is correct
36 Correct 243 ms 45100 KB Output is correct
37 Correct 363 ms 45128 KB Output is correct
38 Correct 270 ms 42504 KB Output is correct
39 Correct 346 ms 43292 KB Output is correct
40 Correct 323 ms 39928 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30288 KB Output is correct
2 Correct 5 ms 30288 KB Output is correct
3 Correct 5 ms 30456 KB Output is correct
4 Correct 5 ms 30288 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30288 KB Output is correct
7 Correct 5 ms 30288 KB Output is correct
8 Correct 4 ms 30288 KB Output is correct
9 Correct 5 ms 30288 KB Output is correct
10 Correct 5 ms 30288 KB Output is correct
11 Incorrect 119 ms 49476 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30288 KB Output is correct
2 Correct 5 ms 30288 KB Output is correct
3 Correct 5 ms 30456 KB Output is correct
4 Correct 5 ms 30288 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30288 KB Output is correct
7 Correct 5 ms 30288 KB Output is correct
8 Correct 4 ms 30288 KB Output is correct
9 Correct 5 ms 30288 KB Output is correct
10 Correct 5 ms 30288 KB Output is correct
11 Correct 251 ms 34312 KB Output is correct
12 Correct 227 ms 33864 KB Output is correct
13 Correct 222 ms 33096 KB Output is correct
14 Correct 224 ms 33352 KB Output is correct
15 Correct 238 ms 34588 KB Output is correct
16 Correct 249 ms 33328 KB Output is correct
17 Correct 257 ms 33352 KB Output is correct
18 Correct 279 ms 35172 KB Output is correct
19 Correct 210 ms 32188 KB Output is correct
20 Correct 261 ms 33804 KB Output is correct
21 Correct 414 ms 34376 KB Output is correct
22 Correct 407 ms 34460 KB Output is correct
23 Correct 341 ms 47100 KB Output is correct
24 Correct 346 ms 40512 KB Output is correct
25 Correct 468 ms 42036 KB Output is correct
26 Correct 366 ms 44616 KB Output is correct
27 Correct 335 ms 33784 KB Output is correct
28 Correct 1609 ms 40116 KB Output is correct
29 Correct 267 ms 38728 KB Output is correct
30 Correct 400 ms 41032 KB Output is correct
31 Correct 394 ms 41356 KB Output is correct
32 Correct 387 ms 34380 KB Output is correct
33 Correct 293 ms 37016 KB Output is correct
34 Correct 351 ms 43392 KB Output is correct
35 Correct 380 ms 47504 KB Output is correct
36 Correct 243 ms 45100 KB Output is correct
37 Correct 363 ms 45128 KB Output is correct
38 Correct 270 ms 42504 KB Output is correct
39 Correct 346 ms 43292 KB Output is correct
40 Correct 323 ms 39928 KB Output is correct
41 Incorrect 119 ms 49476 KB Output isn't correct
42 Halted 0 ms 0 KB -