답안 #1115142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115142	2024-11-20T06:49:36 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	822 ms	45124 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)
 
const int B1 = 7;
const int B2 = 20-B1;
const int N1 = (1<<B1)+2;
const int N2 = (1<<B2)+2;
const int M1 = 2190;
const int M2 = 1594325;
vector<array<int,2>> v, w[N1];
string s;
bitset<N1+10> submask[M1];
int l, q, ans[M2], dp[M2], nx[2][M2];
 
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;
	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;
	memset(nx,-1,sizeof(nx));
	for(int i = 0; i < M2; i++){
		int xd = i, p = 1;
		while(xd){
			int r = xd%3;
			if(r==2){
				nx[0][i] = i-2*p; 
				nx[1][i] = i-p; break;
			}
			xd/=3; p*=3;
		}
	}
	for(int i = 0; i < M1; i++){
		for(int j = 0; j < N1; j++){
			int ok = 1, cur = i, cur2 = j;
			for(int k = 0; k < B1; k++){
				int t = cur%3, t2=cur2%2; cur/=3; cur2/=2;
				if(t==2 or t==t2) continue; ok=0; break;
			}
			if(ok) submask[i][j]=1;
		}
	}
	for(int mask = 0; mask < (1<<l); mask++){
		int m1 = 0, m2 = mask;
		if(l>B1) m1 = mask&((1<<B1)-1), m2>>=B1;
		w[m1].pb({calc(m2),s[mask]-'0'});
	}
	for(int i = 0; i < q; i++){
		string t; cin >> t; 
		reverse(all(t)); string x="";
		if(l>B1) x = t.substr(0,B1),t=t.substr(B1);
		v.pb({calc(x),calc(t)});
	}
	for(int _ = 0; _ < N1; _++){
		memset(dp,0,sizeof(dp));
		for(auto [xd,sc] : w[_]) dp[xd]+=sc;
		for(int i = 0; i < M2; i++)
			if(nx[0][i]!=-1) dp[i]+=dp[nx[0][i]]+dp[nx[1][i]];
		for(int i = 0; i < q; i++){
			auto [x,y] = v[i];
			if(submask[x][_]) ans[i]+=dp[y];
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Compilation message

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:55:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |     if(t==2 or t==t2) continue; ok=0; break;
      |     ^~
snake_escaping.cpp:55:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |     if(t==2 or t==t2) continue; ok=0; break;
      |                                 ^~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21072 KB	Output is correct
2	Correct	232 ms	21220 KB	Output is correct
3	Correct	219 ms	21232 KB	Output is correct
4	Correct	224 ms	21244 KB	Output is correct
5	Correct	235 ms	21252 KB	Output is correct
6	Correct	212 ms	21244 KB	Output is correct
7	Correct	225 ms	21072 KB	Output is correct
8	Correct	244 ms	21332 KB	Output is correct
9	Correct	243 ms	21072 KB	Output is correct
10	Correct	222 ms	21248 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21072 KB	Output is correct
2	Correct	232 ms	21220 KB	Output is correct
3	Correct	219 ms	21232 KB	Output is correct
4	Correct	224 ms	21244 KB	Output is correct
5	Correct	235 ms	21252 KB	Output is correct
6	Correct	212 ms	21244 KB	Output is correct
7	Correct	225 ms	21072 KB	Output is correct
8	Correct	244 ms	21332 KB	Output is correct
9	Correct	243 ms	21072 KB	Output is correct
10	Correct	222 ms	21248 KB	Output is correct
11	Correct	664 ms	41140 KB	Output is correct
12	Correct	696 ms	40888 KB	Output is correct
13	Correct	626 ms	40068 KB	Output is correct
14	Correct	626 ms	40116 KB	Output is correct
15	Correct	760 ms	41084 KB	Output is correct
16	Correct	638 ms	40316 KB	Output is correct
17	Correct	604 ms	40324 KB	Output is correct
18	Correct	531 ms	42168 KB	Output is correct
19	Correct	541 ms	39236 KB	Output is correct
20	Correct	663 ms	40884 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21072 KB	Output is correct
2	Correct	232 ms	21220 KB	Output is correct
3	Correct	219 ms	21232 KB	Output is correct
4	Correct	224 ms	21244 KB	Output is correct
5	Correct	235 ms	21252 KB	Output is correct
6	Correct	212 ms	21244 KB	Output is correct
7	Correct	225 ms	21072 KB	Output is correct
8	Correct	244 ms	21332 KB	Output is correct
9	Correct	243 ms	21072 KB	Output is correct
10	Correct	222 ms	21248 KB	Output is correct
11	Correct	664 ms	41140 KB	Output is correct
12	Correct	696 ms	40888 KB	Output is correct
13	Correct	626 ms	40068 KB	Output is correct
14	Correct	626 ms	40116 KB	Output is correct
15	Correct	760 ms	41084 KB	Output is correct
16	Correct	638 ms	40316 KB	Output is correct
17	Correct	604 ms	40324 KB	Output is correct
18	Correct	531 ms	42168 KB	Output is correct
19	Correct	541 ms	39236 KB	Output is correct
20	Correct	663 ms	40884 KB	Output is correct
21	Correct	652 ms	42664 KB	Output is correct
22	Correct	725 ms	42660 KB	Output is correct
23	Correct	614 ms	41900 KB	Output is correct
24	Correct	604 ms	41668 KB	Output is correct
25	Correct	822 ms	43708 KB	Output is correct
26	Correct	626 ms	42152 KB	Output is correct
27	Correct	618 ms	42172 KB	Output is correct
28	Correct	546 ms	45124 KB	Output is correct
29	Correct	626 ms	40892 KB	Output is correct
30	Correct	731 ms	42428 KB	Output is correct
31	Correct	658 ms	42664 KB	Output is correct
32	Correct	631 ms	42660 KB	Output is correct
33	Correct	580 ms	41552 KB	Output is correct
34	Correct	546 ms	41380 KB	Output is correct
35	Correct	580 ms	42156 KB	Output is correct
36	Correct	542 ms	40664 KB	Output is correct
37	Correct	691 ms	42660 KB	Output is correct
38	Correct	664 ms	40612 KB	Output is correct
39	Correct	631 ms	41892 KB	Output is correct
40	Correct	604 ms	41796 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21072 KB	Output is correct
2	Correct	232 ms	21220 KB	Output is correct
3	Correct	219 ms	21232 KB	Output is correct
4	Correct	224 ms	21244 KB	Output is correct
5	Correct	235 ms	21252 KB	Output is correct
6	Correct	212 ms	21244 KB	Output is correct
7	Correct	225 ms	21072 KB	Output is correct
8	Correct	244 ms	21332 KB	Output is correct
9	Correct	243 ms	21072 KB	Output is correct
10	Correct	222 ms	21248 KB	Output is correct
11	Incorrect	271 ms	33892 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21072 KB	Output is correct
2	Correct	232 ms	21220 KB	Output is correct
3	Correct	219 ms	21232 KB	Output is correct
4	Correct	224 ms	21244 KB	Output is correct
5	Correct	235 ms	21252 KB	Output is correct
6	Correct	212 ms	21244 KB	Output is correct
7	Correct	225 ms	21072 KB	Output is correct
8	Correct	244 ms	21332 KB	Output is correct
9	Correct	243 ms	21072 KB	Output is correct
10	Correct	222 ms	21248 KB	Output is correct
11	Correct	664 ms	41140 KB	Output is correct
12	Correct	696 ms	40888 KB	Output is correct
13	Correct	626 ms	40068 KB	Output is correct
14	Correct	626 ms	40116 KB	Output is correct
15	Correct	760 ms	41084 KB	Output is correct
16	Correct	638 ms	40316 KB	Output is correct
17	Correct	604 ms	40324 KB	Output is correct
18	Correct	531 ms	42168 KB	Output is correct
19	Correct	541 ms	39236 KB	Output is correct
20	Correct	663 ms	40884 KB	Output is correct
21	Correct	652 ms	42664 KB	Output is correct
22	Correct	725 ms	42660 KB	Output is correct
23	Correct	614 ms	41900 KB	Output is correct
24	Correct	604 ms	41668 KB	Output is correct
25	Correct	822 ms	43708 KB	Output is correct
26	Correct	626 ms	42152 KB	Output is correct
27	Correct	618 ms	42172 KB	Output is correct
28	Correct	546 ms	45124 KB	Output is correct
29	Correct	626 ms	40892 KB	Output is correct
30	Correct	731 ms	42428 KB	Output is correct
31	Correct	658 ms	42664 KB	Output is correct
32	Correct	631 ms	42660 KB	Output is correct
33	Correct	580 ms	41552 KB	Output is correct
34	Correct	546 ms	41380 KB	Output is correct
35	Correct	580 ms	42156 KB	Output is correct
36	Correct	542 ms	40664 KB	Output is correct
37	Correct	691 ms	42660 KB	Output is correct
38	Correct	664 ms	40612 KB	Output is correct
39	Correct	631 ms	41892 KB	Output is correct
40	Correct	604 ms	41796 KB	Output is correct
41	Incorrect	271 ms	33892 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #1115142

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