Submission #1114715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1114715	2024-11-19T13:09:57 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	644 ms	65536 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	8 ms	57936 KB	Output is correct
3	Correct	7 ms	55888 KB	Output is correct
4	Correct	6 ms	57936 KB	Output is correct
5	Correct	7 ms	61960 KB	Output is correct
6	Correct	6 ms	50000 KB	Output is correct
7	Correct	6 ms	50000 KB	Output is correct
8	Correct	7 ms	54124 KB	Output is correct
9	Correct	6 ms	50000 KB	Output is correct
10	Correct	7 ms	54048 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	8 ms	57936 KB	Output is correct
3	Correct	7 ms	55888 KB	Output is correct
4	Correct	6 ms	57936 KB	Output is correct
5	Correct	7 ms	61960 KB	Output is correct
6	Correct	6 ms	50000 KB	Output is correct
7	Correct	6 ms	50000 KB	Output is correct
8	Correct	7 ms	54124 KB	Output is correct
9	Correct	6 ms	50000 KB	Output is correct
10	Correct	7 ms	54048 KB	Output is correct
11	Correct	289 ms	59976 KB	Output is correct
12	Correct	279 ms	49736 KB	Output is correct
13	Correct	257 ms	61000 KB	Output is correct
14	Correct	261 ms	47176 KB	Output is correct
15	Correct	302 ms	46200 KB	Output is correct
16	Correct	265 ms	41288 KB	Output is correct
17	Correct	276 ms	49232 KB	Output is correct
18	Correct	358 ms	49124 KB	Output is correct
19	Correct	222 ms	44104 KB	Output is correct
20	Correct	285 ms	45760 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	8 ms	57936 KB	Output is correct
3	Correct	7 ms	55888 KB	Output is correct
4	Correct	6 ms	57936 KB	Output is correct
5	Correct	7 ms	61960 KB	Output is correct
6	Correct	6 ms	50000 KB	Output is correct
7	Correct	6 ms	50000 KB	Output is correct
8	Correct	7 ms	54124 KB	Output is correct
9	Correct	6 ms	50000 KB	Output is correct
10	Correct	7 ms	54048 KB	Output is correct
11	Correct	289 ms	59976 KB	Output is correct
12	Correct	279 ms	49736 KB	Output is correct
13	Correct	257 ms	61000 KB	Output is correct
14	Correct	261 ms	47176 KB	Output is correct
15	Correct	302 ms	46200 KB	Output is correct
16	Correct	265 ms	41288 KB	Output is correct
17	Correct	276 ms	49232 KB	Output is correct
18	Correct	358 ms	49124 KB	Output is correct
19	Correct	222 ms	44104 KB	Output is correct
20	Correct	285 ms	45760 KB	Output is correct
21	Correct	447 ms	46236 KB	Output is correct
22	Correct	512 ms	59852 KB	Output is correct
23	Correct	335 ms	54856 KB	Output is correct
24	Correct	345 ms	58876 KB	Output is correct
25	Correct	644 ms	58696 KB	Output is correct
26	Correct	385 ms	59336 KB	Output is correct
27	Correct	396 ms	61256 KB	Output is correct
28	Correct	226 ms	65536 KB	Output is correct
29	Correct	262 ms	65536 KB	Output is correct
30	Correct	505 ms	63936 KB	Output is correct
31	Correct	430 ms	61768 KB	Output is correct
32	Correct	390 ms	65536 KB	Output is correct
33	Correct	299 ms	65536 KB	Output is correct
34	Correct	357 ms	62176 KB	Output is correct
35	Correct	379 ms	63304 KB	Output is correct
36	Correct	212 ms	57912 KB	Output is correct
37	Correct	391 ms	65536 KB	Output is correct
38	Correct	267 ms	57708 KB	Output is correct
39	Correct	355 ms	57160 KB	Output is correct
40	Correct	341 ms	60744 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	8 ms	57936 KB	Output is correct
3	Correct	7 ms	55888 KB	Output is correct
4	Correct	6 ms	57936 KB	Output is correct
5	Correct	7 ms	61960 KB	Output is correct
6	Correct	6 ms	50000 KB	Output is correct
7	Correct	6 ms	50000 KB	Output is correct
8	Correct	7 ms	54124 KB	Output is correct
9	Correct	6 ms	50000 KB	Output is correct
10	Correct	7 ms	54048 KB	Output is correct
11	Incorrect	627 ms	65256 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	8 ms	57936 KB	Output is correct
3	Correct	7 ms	55888 KB	Output is correct
4	Correct	6 ms	57936 KB	Output is correct
5	Correct	7 ms	61960 KB	Output is correct
6	Correct	6 ms	50000 KB	Output is correct
7	Correct	6 ms	50000 KB	Output is correct
8	Correct	7 ms	54124 KB	Output is correct
9	Correct	6 ms	50000 KB	Output is correct
10	Correct	7 ms	54048 KB	Output is correct
11	Correct	289 ms	59976 KB	Output is correct
12	Correct	279 ms	49736 KB	Output is correct
13	Correct	257 ms	61000 KB	Output is correct
14	Correct	261 ms	47176 KB	Output is correct
15	Correct	302 ms	46200 KB	Output is correct
16	Correct	265 ms	41288 KB	Output is correct
17	Correct	276 ms	49232 KB	Output is correct
18	Correct	358 ms	49124 KB	Output is correct
19	Correct	222 ms	44104 KB	Output is correct
20	Correct	285 ms	45760 KB	Output is correct
21	Correct	447 ms	46236 KB	Output is correct
22	Correct	512 ms	59852 KB	Output is correct
23	Correct	335 ms	54856 KB	Output is correct
24	Correct	345 ms	58876 KB	Output is correct
25	Correct	644 ms	58696 KB	Output is correct
26	Correct	385 ms	59336 KB	Output is correct
27	Correct	396 ms	61256 KB	Output is correct
28	Correct	226 ms	65536 KB	Output is correct
29	Correct	262 ms	65536 KB	Output is correct
30	Correct	505 ms	63936 KB	Output is correct
31	Correct	430 ms	61768 KB	Output is correct
32	Correct	390 ms	65536 KB	Output is correct
33	Correct	299 ms	65536 KB	Output is correct
34	Correct	357 ms	62176 KB	Output is correct
35	Correct	379 ms	63304 KB	Output is correct
36	Correct	212 ms	57912 KB	Output is correct
37	Correct	391 ms	65536 KB	Output is correct
38	Correct	267 ms	57708 KB	Output is correct
39	Correct	355 ms	57160 KB	Output is correct
40	Correct	341 ms	60744 KB	Output is correct
41	Incorrect	627 ms	65256 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #1114715

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