Submission #1114718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114718	2024-11-19T13:12:03 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	623 ms	65024 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 = 5;
const int B2 = 20-B1;
const int N = p3[B1];
int pre[N][1<<B2], 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;
	for(int i = 0; i < B1; i++)
		ans+=(lol>>i&1)*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 t = mask2; ; t--,t&=mask2){
			pre[mask1][t]+=sc; if(!t) break;
		}
	}
	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++){
			pre[mask2][i]+=pre[mask1][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 = pre[x][0];
			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	7 ms	62032 KB	Output is correct
2	Correct	7 ms	58104 KB	Output is correct
3	Correct	6 ms	52048 KB	Output is correct
4	Correct	6 ms	48116 KB	Output is correct
5	Correct	5 ms	40360 KB	Output is correct
6	Correct	5 ms	32080 KB	Output is correct
7	Correct	5 ms	34128 KB	Output is correct
8	Correct	4 ms	28240 KB	Output is correct
9	Correct	5 ms	28240 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	7 ms	62032 KB	Output is correct
2	Correct	7 ms	58104 KB	Output is correct
3	Correct	6 ms	52048 KB	Output is correct
4	Correct	6 ms	48116 KB	Output is correct
5	Correct	5 ms	40360 KB	Output is correct
6	Correct	5 ms	32080 KB	Output is correct
7	Correct	5 ms	34128 KB	Output is correct
8	Correct	4 ms	28240 KB	Output is correct
9	Correct	5 ms	28240 KB	Output is correct
10	Correct	5 ms	30288 KB	Output is correct
11	Correct	272 ms	36140 KB	Output is correct
12	Correct	282 ms	47836 KB	Output is correct
13	Correct	234 ms	31100 KB	Output is correct
14	Correct	250 ms	33136 KB	Output is correct
15	Correct	274 ms	40264 KB	Output is correct
16	Correct	254 ms	43336 KB	Output is correct
17	Correct	295 ms	51272 KB	Output is correct
18	Correct	392 ms	47176 KB	Output is correct
19	Correct	226 ms	40016 KB	Output is correct
20	Correct	292 ms	47868 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	62032 KB	Output is correct
2	Correct	7 ms	58104 KB	Output is correct
3	Correct	6 ms	52048 KB	Output is correct
4	Correct	6 ms	48116 KB	Output is correct
5	Correct	5 ms	40360 KB	Output is correct
6	Correct	5 ms	32080 KB	Output is correct
7	Correct	5 ms	34128 KB	Output is correct
8	Correct	4 ms	28240 KB	Output is correct
9	Correct	5 ms	28240 KB	Output is correct
10	Correct	5 ms	30288 KB	Output is correct
11	Correct	272 ms	36140 KB	Output is correct
12	Correct	282 ms	47836 KB	Output is correct
13	Correct	234 ms	31100 KB	Output is correct
14	Correct	250 ms	33136 KB	Output is correct
15	Correct	274 ms	40264 KB	Output is correct
16	Correct	254 ms	43336 KB	Output is correct
17	Correct	295 ms	51272 KB	Output is correct
18	Correct	392 ms	47176 KB	Output is correct
19	Correct	226 ms	40016 KB	Output is correct
20	Correct	292 ms	47868 KB	Output is correct
21	Correct	472 ms	50028 KB	Output is correct
22	Correct	517 ms	52304 KB	Output is correct
23	Correct	360 ms	49304 KB	Output is correct
24	Correct	342 ms	49072 KB	Output is correct
25	Correct	617 ms	45260 KB	Output is correct
26	Correct	395 ms	45640 KB	Output is correct
27	Correct	373 ms	41692 KB	Output is correct
28	Correct	219 ms	44104 KB	Output is correct
29	Correct	240 ms	36424 KB	Output is correct
30	Correct	483 ms	42184 KB	Output is correct
31	Correct	390 ms	42084 KB	Output is correct
32	Correct	372 ms	42364 KB	Output is correct
33	Correct	329 ms	46156 KB	Output is correct
34	Correct	356 ms	45128 KB	Output is correct
35	Correct	412 ms	45640 KB	Output is correct
36	Correct	204 ms	42056 KB	Output is correct
37	Correct	383 ms	50136 KB	Output is correct
38	Correct	259 ms	42056 KB	Output is correct
39	Correct	335 ms	39352 KB	Output is correct
40	Correct	337 ms	39104 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	62032 KB	Output is correct
2	Correct	7 ms	58104 KB	Output is correct
3	Correct	6 ms	52048 KB	Output is correct
4	Correct	6 ms	48116 KB	Output is correct
5	Correct	5 ms	40360 KB	Output is correct
6	Correct	5 ms	32080 KB	Output is correct
7	Correct	5 ms	34128 KB	Output is correct
8	Correct	4 ms	28240 KB	Output is correct
9	Correct	5 ms	28240 KB	Output is correct
10	Correct	5 ms	30288 KB	Output is correct
11	Incorrect	623 ms	65024 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	62032 KB	Output is correct
2	Correct	7 ms	58104 KB	Output is correct
3	Correct	6 ms	52048 KB	Output is correct
4	Correct	6 ms	48116 KB	Output is correct
5	Correct	5 ms	40360 KB	Output is correct
6	Correct	5 ms	32080 KB	Output is correct
7	Correct	5 ms	34128 KB	Output is correct
8	Correct	4 ms	28240 KB	Output is correct
9	Correct	5 ms	28240 KB	Output is correct
10	Correct	5 ms	30288 KB	Output is correct
11	Correct	272 ms	36140 KB	Output is correct
12	Correct	282 ms	47836 KB	Output is correct
13	Correct	234 ms	31100 KB	Output is correct
14	Correct	250 ms	33136 KB	Output is correct
15	Correct	274 ms	40264 KB	Output is correct
16	Correct	254 ms	43336 KB	Output is correct
17	Correct	295 ms	51272 KB	Output is correct
18	Correct	392 ms	47176 KB	Output is correct
19	Correct	226 ms	40016 KB	Output is correct
20	Correct	292 ms	47868 KB	Output is correct
21	Correct	472 ms	50028 KB	Output is correct
22	Correct	517 ms	52304 KB	Output is correct
23	Correct	360 ms	49304 KB	Output is correct
24	Correct	342 ms	49072 KB	Output is correct
25	Correct	617 ms	45260 KB	Output is correct
26	Correct	395 ms	45640 KB	Output is correct
27	Correct	373 ms	41692 KB	Output is correct
28	Correct	219 ms	44104 KB	Output is correct
29	Correct	240 ms	36424 KB	Output is correct
30	Correct	483 ms	42184 KB	Output is correct
31	Correct	390 ms	42084 KB	Output is correct
32	Correct	372 ms	42364 KB	Output is correct
33	Correct	329 ms	46156 KB	Output is correct
34	Correct	356 ms	45128 KB	Output is correct
35	Correct	412 ms	45640 KB	Output is correct
36	Correct	204 ms	42056 KB	Output is correct
37	Correct	383 ms	50136 KB	Output is correct
38	Correct	259 ms	42056 KB	Output is correct
39	Correct	335 ms	39352 KB	Output is correct
40	Correct	337 ms	39104 KB	Output is correct
41	Incorrect	623 ms	65024 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #1114718

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