답안 #1115149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115149	2024-11-20T07:12:00 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1609 ms	49476 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];
 
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1115149

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