답안 #1115143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115143	2024-11-20T06:50:55 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	745 ms	37548 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)+10;
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-9; _++){
		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	21084 KB	Output is correct
2	Correct	224 ms	21072 KB	Output is correct
3	Correct	248 ms	21072 KB	Output is correct
4	Correct	221 ms	21248 KB	Output is correct
5	Correct	230 ms	21072 KB	Output is correct
6	Correct	216 ms	21240 KB	Output is correct
7	Correct	208 ms	21072 KB	Output is correct
8	Correct	224 ms	21228 KB	Output is correct
9	Correct	212 ms	21072 KB	Output is correct
10	Correct	209 ms	21240 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21084 KB	Output is correct
2	Correct	224 ms	21072 KB	Output is correct
3	Correct	248 ms	21072 KB	Output is correct
4	Correct	221 ms	21248 KB	Output is correct
5	Correct	230 ms	21072 KB	Output is correct
6	Correct	216 ms	21240 KB	Output is correct
7	Correct	208 ms	21072 KB	Output is correct
8	Correct	224 ms	21228 KB	Output is correct
9	Correct	212 ms	21072 KB	Output is correct
10	Correct	209 ms	21240 KB	Output is correct
11	Correct	602 ms	35456 KB	Output is correct
12	Correct	704 ms	35196 KB	Output is correct
13	Correct	594 ms	34428 KB	Output is correct
14	Correct	598 ms	34628 KB	Output is correct
15	Correct	745 ms	35460 KB	Output is correct
16	Correct	613 ms	34688 KB	Output is correct
17	Correct	594 ms	34692 KB	Output is correct
18	Correct	511 ms	36508 KB	Output is correct
19	Correct	620 ms	33460 KB	Output is correct
20	Correct	693 ms	35252 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21084 KB	Output is correct
2	Correct	224 ms	21072 KB	Output is correct
3	Correct	248 ms	21072 KB	Output is correct
4	Correct	221 ms	21248 KB	Output is correct
5	Correct	230 ms	21072 KB	Output is correct
6	Correct	216 ms	21240 KB	Output is correct
7	Correct	208 ms	21072 KB	Output is correct
8	Correct	224 ms	21228 KB	Output is correct
9	Correct	212 ms	21072 KB	Output is correct
10	Correct	209 ms	21240 KB	Output is correct
11	Correct	602 ms	35456 KB	Output is correct
12	Correct	704 ms	35196 KB	Output is correct
13	Correct	594 ms	34428 KB	Output is correct
14	Correct	598 ms	34628 KB	Output is correct
15	Correct	745 ms	35460 KB	Output is correct
16	Correct	613 ms	34688 KB	Output is correct
17	Correct	594 ms	34692 KB	Output is correct
18	Correct	511 ms	36508 KB	Output is correct
19	Correct	620 ms	33460 KB	Output is correct
20	Correct	693 ms	35252 KB	Output is correct
21	Correct	697 ms	35516 KB	Output is correct
22	Correct	712 ms	35752 KB	Output is correct
23	Correct	567 ms	34724 KB	Output is correct
24	Correct	547 ms	34492 KB	Output is correct
25	Correct	738 ms	36536 KB	Output is correct
26	Correct	611 ms	35000 KB	Output is correct
27	Correct	629 ms	35008 KB	Output is correct
28	Correct	508 ms	37548 KB	Output is correct
29	Correct	563 ms	33448 KB	Output is correct
30	Correct	702 ms	35776 KB	Output is correct
31	Correct	669 ms	35480 KB	Output is correct
32	Correct	666 ms	35496 KB	Output is correct
33	Correct	620 ms	34468 KB	Output is correct
34	Correct	622 ms	34500 KB	Output is correct
35	Correct	619 ms	35000 KB	Output is correct
36	Correct	522 ms	33444 KB	Output is correct
37	Correct	642 ms	35520 KB	Output is correct
38	Correct	562 ms	33468 KB	Output is correct
39	Correct	553 ms	34748 KB	Output is correct
40	Correct	555 ms	34488 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21084 KB	Output is correct
2	Correct	224 ms	21072 KB	Output is correct
3	Correct	248 ms	21072 KB	Output is correct
4	Correct	221 ms	21248 KB	Output is correct
5	Correct	230 ms	21072 KB	Output is correct
6	Correct	216 ms	21240 KB	Output is correct
7	Correct	208 ms	21072 KB	Output is correct
8	Correct	224 ms	21228 KB	Output is correct
9	Correct	212 ms	21072 KB	Output is correct
10	Correct	209 ms	21240 KB	Output is correct
11	Incorrect	269 ms	32488 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	21084 KB	Output is correct
2	Correct	224 ms	21072 KB	Output is correct
3	Correct	248 ms	21072 KB	Output is correct
4	Correct	221 ms	21248 KB	Output is correct
5	Correct	230 ms	21072 KB	Output is correct
6	Correct	216 ms	21240 KB	Output is correct
7	Correct	208 ms	21072 KB	Output is correct
8	Correct	224 ms	21228 KB	Output is correct
9	Correct	212 ms	21072 KB	Output is correct
10	Correct	209 ms	21240 KB	Output is correct
11	Correct	602 ms	35456 KB	Output is correct
12	Correct	704 ms	35196 KB	Output is correct
13	Correct	594 ms	34428 KB	Output is correct
14	Correct	598 ms	34628 KB	Output is correct
15	Correct	745 ms	35460 KB	Output is correct
16	Correct	613 ms	34688 KB	Output is correct
17	Correct	594 ms	34692 KB	Output is correct
18	Correct	511 ms	36508 KB	Output is correct
19	Correct	620 ms	33460 KB	Output is correct
20	Correct	693 ms	35252 KB	Output is correct
21	Correct	697 ms	35516 KB	Output is correct
22	Correct	712 ms	35752 KB	Output is correct
23	Correct	567 ms	34724 KB	Output is correct
24	Correct	547 ms	34492 KB	Output is correct
25	Correct	738 ms	36536 KB	Output is correct
26	Correct	611 ms	35000 KB	Output is correct
27	Correct	629 ms	35008 KB	Output is correct
28	Correct	508 ms	37548 KB	Output is correct
29	Correct	563 ms	33448 KB	Output is correct
30	Correct	702 ms	35776 KB	Output is correct
31	Correct	669 ms	35480 KB	Output is correct
32	Correct	666 ms	35496 KB	Output is correct
33	Correct	620 ms	34468 KB	Output is correct
34	Correct	622 ms	34500 KB	Output is correct
35	Correct	619 ms	35000 KB	Output is correct
36	Correct	522 ms	33444 KB	Output is correct
37	Correct	642 ms	35520 KB	Output is correct
38	Correct	562 ms	33468 KB	Output is correct
39	Correct	553 ms	34748 KB	Output is correct
40	Correct	555 ms	34488 KB	Output is correct
41	Incorrect	269 ms	32488 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #1115143

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