oj.uz

Submission #1115157

# Submission time Handle Problem Language Result Execution time Memory
1115157 2024-11-20T07:22:35 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 1301 ms 49384 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};
int B1 = 6;
const int B2 = 20-6;
const int N = p3[6];
int score[N+2][(1<<B2)+2];
 
int calc(string lol){
	int p = 1, ans = 0, xd;
	for(int i = 0; i < sz(lol); 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;
	}*/
	B1=min(B1,l-1); 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 30292 KB Output is correct
3 Correct 6 ms 30288 KB Output is correct
4 Correct 5 ms 30300 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30236 KB Output is correct
7 Correct 5 ms 30456 KB Output is correct
8 Correct 6 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 30292 KB Output is correct
3 Correct 6 ms 30288 KB Output is correct
4 Correct 5 ms 30300 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30236 KB Output is correct
7 Correct 5 ms 30456 KB Output is correct
8 Correct 6 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 239 ms 34244 KB Output is correct
12 Correct 239 ms 33872 KB Output is correct
13 Correct 229 ms 33096 KB Output is correct
14 Correct 234 ms 33352 KB Output is correct
15 Correct 249 ms 34384 KB Output is correct
16 Correct 238 ms 33372 KB Output is correct
17 Correct 249 ms 33352 KB Output is correct
18 Correct 238 ms 35144 KB Output is correct
19 Correct 195 ms 32328 KB Output is correct
20 Correct 246 ms 33968 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 30292 KB Output is correct
3 Correct 6 ms 30288 KB Output is correct
4 Correct 5 ms 30300 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30236 KB Output is correct
7 Correct 5 ms 30456 KB Output is correct
8 Correct 6 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 239 ms 34244 KB Output is correct
12 Correct 239 ms 33872 KB Output is correct
13 Correct 229 ms 33096 KB Output is correct
14 Correct 234 ms 33352 KB Output is correct
15 Correct 249 ms 34384 KB Output is correct
16 Correct 238 ms 33372 KB Output is correct
17 Correct 249 ms 33352 KB Output is correct
18 Correct 238 ms 35144 KB Output is correct
19 Correct 195 ms 32328 KB Output is correct
20 Correct 246 ms 33968 KB Output is correct
21 Correct 386 ms 34376 KB Output is correct
22 Correct 425 ms 34488 KB Output is correct
23 Correct 342 ms 33608 KB Output is correct
24 Correct 377 ms 33344 KB Output is correct
25 Correct 451 ms 35312 KB Output is correct
26 Correct 365 ms 33872 KB Output is correct
27 Correct 378 ms 33864 KB Output is correct
28 Correct 1301 ms 36392 KB Output is correct
29 Correct 241 ms 32328 KB Output is correct
30 Correct 392 ms 34532 KB Output is correct
31 Correct 355 ms 34376 KB Output is correct
32 Correct 329 ms 34500 KB Output is correct
33 Correct 291 ms 33300 KB Output is correct
34 Correct 318 ms 33352 KB Output is correct
35 Correct 371 ms 33864 KB Output is correct
36 Correct 213 ms 32328 KB Output is correct
37 Correct 337 ms 34444 KB Output is correct
38 Correct 262 ms 32328 KB Output is correct
39 Correct 339 ms 33608 KB Output is correct
40 Correct 354 ms 33360 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 30292 KB Output is correct
3 Correct 6 ms 30288 KB Output is correct
4 Correct 5 ms 30300 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30236 KB Output is correct
7 Correct 5 ms 30456 KB Output is correct
8 Correct 6 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 121 ms 49384 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 30292 KB Output is correct
3 Correct 6 ms 30288 KB Output is correct
4 Correct 5 ms 30300 KB Output is correct
5 Correct 5 ms 30288 KB Output is correct
6 Correct 5 ms 30236 KB Output is correct
7 Correct 5 ms 30456 KB Output is correct
8 Correct 6 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 239 ms 34244 KB Output is correct
12 Correct 239 ms 33872 KB Output is correct
13 Correct 229 ms 33096 KB Output is correct
14 Correct 234 ms 33352 KB Output is correct
15 Correct 249 ms 34384 KB Output is correct
16 Correct 238 ms 33372 KB Output is correct
17 Correct 249 ms 33352 KB Output is correct
18 Correct 238 ms 35144 KB Output is correct
19 Correct 195 ms 32328 KB Output is correct
20 Correct 246 ms 33968 KB Output is correct
21 Correct 386 ms 34376 KB Output is correct
22 Correct 425 ms 34488 KB Output is correct
23 Correct 342 ms 33608 KB Output is correct
24 Correct 377 ms 33344 KB Output is correct
25 Correct 451 ms 35312 KB Output is correct
26 Correct 365 ms 33872 KB Output is correct
27 Correct 378 ms 33864 KB Output is correct
28 Correct 1301 ms 36392 KB Output is correct
29 Correct 241 ms 32328 KB Output is correct
30 Correct 392 ms 34532 KB Output is correct
31 Correct 355 ms 34376 KB Output is correct
32 Correct 329 ms 34500 KB Output is correct
33 Correct 291 ms 33300 KB Output is correct
34 Correct 318 ms 33352 KB Output is correct
35 Correct 371 ms 33864 KB Output is correct
36 Correct 213 ms 32328 KB Output is correct
37 Correct 337 ms 34444 KB Output is correct
38 Correct 262 ms 32328 KB Output is correct
39 Correct 339 ms 33608 KB Output is correct
40 Correct 354 ms 33360 KB Output is correct
41 Incorrect 121 ms 49384 KB Output isn't correct
42 Halted 0 ms 0 KB -