Submission #1115151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115151	2024-11-20T07:14:35 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1355 ms	56148 KB

snake_escaping

#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], tot[N];
 
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';
		tot[mask1]+=sc;
		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;
		tot[mask2]+=tot[mask1];
		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); ans = tot[x];
			for(int mask = 1; 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	6 ms	45648 KB	Output is correct
2	Correct	6 ms	45648 KB	Output is correct
3	Correct	6 ms	45816 KB	Output is correct
4	Correct	6 ms	45648 KB	Output is correct
5	Correct	7 ms	45720 KB	Output is correct
6	Correct	7 ms	45816 KB	Output is correct
7	Correct	6 ms	45648 KB	Output is correct
8	Correct	6 ms	45816 KB	Output is correct
9	Correct	6 ms	45648 KB	Output is correct
10	Correct	6 ms	45648 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	45648 KB	Output is correct
2	Correct	6 ms	45648 KB	Output is correct
3	Correct	6 ms	45816 KB	Output is correct
4	Correct	6 ms	45648 KB	Output is correct
5	Correct	7 ms	45720 KB	Output is correct
6	Correct	7 ms	45816 KB	Output is correct
7	Correct	6 ms	45648 KB	Output is correct
8	Correct	6 ms	45816 KB	Output is correct
9	Correct	6 ms	45648 KB	Output is correct
10	Correct	6 ms	45648 KB	Output is correct
11	Correct	249 ms	49480 KB	Output is correct
12	Correct	241 ms	49224 KB	Output is correct
13	Correct	253 ms	48500 KB	Output is correct
14	Correct	257 ms	49316 KB	Output is correct
15	Correct	257 ms	50000 KB	Output is correct
16	Correct	254 ms	53064 KB	Output is correct
17	Correct	249 ms	49328 KB	Output is correct
18	Correct	240 ms	51088 KB	Output is correct
19	Correct	206 ms	47704 KB	Output is correct
20	Correct	233 ms	49224 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	45648 KB	Output is correct
2	Correct	6 ms	45648 KB	Output is correct
3	Correct	6 ms	45816 KB	Output is correct
4	Correct	6 ms	45648 KB	Output is correct
5	Correct	7 ms	45720 KB	Output is correct
6	Correct	7 ms	45816 KB	Output is correct
7	Correct	6 ms	45648 KB	Output is correct
8	Correct	6 ms	45816 KB	Output is correct
9	Correct	6 ms	45648 KB	Output is correct
10	Correct	6 ms	45648 KB	Output is correct
11	Correct	249 ms	49480 KB	Output is correct
12	Correct	241 ms	49224 KB	Output is correct
13	Correct	253 ms	48500 KB	Output is correct
14	Correct	257 ms	49316 KB	Output is correct
15	Correct	257 ms	50000 KB	Output is correct
16	Correct	254 ms	53064 KB	Output is correct
17	Correct	249 ms	49328 KB	Output is correct
18	Correct	240 ms	51088 KB	Output is correct
19	Correct	206 ms	47704 KB	Output is correct
20	Correct	233 ms	49224 KB	Output is correct
21	Correct	355 ms	49736 KB	Output is correct
22	Correct	376 ms	49740 KB	Output is correct
23	Correct	327 ms	55820 KB	Output is correct
24	Correct	324 ms	48712 KB	Output is correct
25	Correct	443 ms	50632 KB	Output is correct
26	Correct	382 ms	54832 KB	Output is correct
27	Correct	351 ms	48968 KB	Output is correct
28	Correct	1355 ms	53704 KB	Output is correct
29	Correct	252 ms	30024 KB	Output is correct
30	Correct	397 ms	30400 KB	Output is correct
31	Correct	391 ms	53448 KB	Output is correct
32	Correct	373 ms	49604 KB	Output is correct
33	Correct	296 ms	51232 KB	Output is correct
34	Correct	323 ms	54072 KB	Output is correct
35	Correct	353 ms	56148 KB	Output is correct
36	Correct	293 ms	54748 KB	Output is correct
37	Correct	338 ms	49736 KB	Output is correct
38	Correct	284 ms	55696 KB	Output is correct
39	Correct	370 ms	51596 KB	Output is correct
40	Correct	344 ms	48712 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	45648 KB	Output is correct
2	Correct	6 ms	45648 KB	Output is correct
3	Correct	6 ms	45816 KB	Output is correct
4	Correct	6 ms	45648 KB	Output is correct
5	Correct	7 ms	45720 KB	Output is correct
6	Correct	7 ms	45816 KB	Output is correct
7	Correct	6 ms	45648 KB	Output is correct
8	Correct	6 ms	45816 KB	Output is correct
9	Correct	6 ms	45648 KB	Output is correct
10	Correct	6 ms	45648 KB	Output is correct
11	Incorrect	116 ms	49640 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	45648 KB	Output is correct
2	Correct	6 ms	45648 KB	Output is correct
3	Correct	6 ms	45816 KB	Output is correct
4	Correct	6 ms	45648 KB	Output is correct
5	Correct	7 ms	45720 KB	Output is correct
6	Correct	7 ms	45816 KB	Output is correct
7	Correct	6 ms	45648 KB	Output is correct
8	Correct	6 ms	45816 KB	Output is correct
9	Correct	6 ms	45648 KB	Output is correct
10	Correct	6 ms	45648 KB	Output is correct
11	Correct	249 ms	49480 KB	Output is correct
12	Correct	241 ms	49224 KB	Output is correct
13	Correct	253 ms	48500 KB	Output is correct
14	Correct	257 ms	49316 KB	Output is correct
15	Correct	257 ms	50000 KB	Output is correct
16	Correct	254 ms	53064 KB	Output is correct
17	Correct	249 ms	49328 KB	Output is correct
18	Correct	240 ms	51088 KB	Output is correct
19	Correct	206 ms	47704 KB	Output is correct
20	Correct	233 ms	49224 KB	Output is correct
21	Correct	355 ms	49736 KB	Output is correct
22	Correct	376 ms	49740 KB	Output is correct
23	Correct	327 ms	55820 KB	Output is correct
24	Correct	324 ms	48712 KB	Output is correct
25	Correct	443 ms	50632 KB	Output is correct
26	Correct	382 ms	54832 KB	Output is correct
27	Correct	351 ms	48968 KB	Output is correct
28	Correct	1355 ms	53704 KB	Output is correct
29	Correct	252 ms	30024 KB	Output is correct
30	Correct	397 ms	30400 KB	Output is correct
31	Correct	391 ms	53448 KB	Output is correct
32	Correct	373 ms	49604 KB	Output is correct
33	Correct	296 ms	51232 KB	Output is correct
34	Correct	323 ms	54072 KB	Output is correct
35	Correct	353 ms	56148 KB	Output is correct
36	Correct	293 ms	54748 KB	Output is correct
37	Correct	338 ms	49736 KB	Output is correct
38	Correct	284 ms	55696 KB	Output is correct
39	Correct	370 ms	51596 KB	Output is correct
40	Correct	344 ms	48712 KB	Output is correct
41	Incorrect	116 ms	49640 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #1115151

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0