답안 #1114787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114787	2024-11-19T15:40:30 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	786 ms	46248 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 N = 1<<B1;
const int B2 = 13;
const int N2 = 1<<B2;
const int M = 1594324;
vector<array<int,2>> v, w[N];
string s;
int l, q, ans[M], dp[M];
int nx[2][M];
bitset<N> submask[2187];

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 < M; 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 < 2187; i++){
		for(int j = 0; j < N; j++){
			int ok = 1, cur = i, cur2 = j;
			for(int k = 0; k < 7; k++){
				int t = cur%3, t2=cur2%2; cur/=3; cur2/=2;
				if(t==2) continue;
				if(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; _ < N; _++){
		if(!sz(v[_])) continue;
		memset(dp,0,sizeof(dp));
		for(auto [xd,sc] : w[_]) dp[xd]+=sc;
		for(int i = 0; i < M; 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";
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	21128 KB	Output is correct
2	Correct	236 ms	21072 KB	Output is correct
3	Correct	234 ms	21072 KB	Output is correct
4	Correct	232 ms	21072 KB	Output is correct
5	Correct	232 ms	21072 KB	Output is correct
6	Correct	229 ms	21088 KB	Output is correct
7	Correct	233 ms	21180 KB	Output is correct
8	Correct	277 ms	21180 KB	Output is correct
9	Correct	247 ms	21072 KB	Output is correct
10	Correct	236 ms	21084 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	21128 KB	Output is correct
2	Correct	236 ms	21072 KB	Output is correct
3	Correct	234 ms	21072 KB	Output is correct
4	Correct	232 ms	21072 KB	Output is correct
5	Correct	232 ms	21072 KB	Output is correct
6	Correct	229 ms	21088 KB	Output is correct
7	Correct	233 ms	21180 KB	Output is correct
8	Correct	277 ms	21180 KB	Output is correct
9	Correct	247 ms	21072 KB	Output is correct
10	Correct	236 ms	21084 KB	Output is correct
11	Correct	693 ms	35548 KB	Output is correct
12	Correct	725 ms	35184 KB	Output is correct
13	Correct	617 ms	34344 KB	Output is correct
14	Correct	591 ms	34488 KB	Output is correct
15	Correct	726 ms	35512 KB	Output is correct
16	Correct	622 ms	40264 KB	Output is correct
17	Correct	606 ms	34636 KB	Output is correct
18	Correct	521 ms	36388 KB	Output is correct
19	Correct	568 ms	33460 KB	Output is correct
20	Correct	662 ms	34996 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	21128 KB	Output is correct
2	Correct	236 ms	21072 KB	Output is correct
3	Correct	234 ms	21072 KB	Output is correct
4	Correct	232 ms	21072 KB	Output is correct
5	Correct	232 ms	21072 KB	Output is correct
6	Correct	229 ms	21088 KB	Output is correct
7	Correct	233 ms	21180 KB	Output is correct
8	Correct	277 ms	21180 KB	Output is correct
9	Correct	247 ms	21072 KB	Output is correct
10	Correct	236 ms	21084 KB	Output is correct
11	Correct	693 ms	35548 KB	Output is correct
12	Correct	725 ms	35184 KB	Output is correct
13	Correct	617 ms	34344 KB	Output is correct
14	Correct	591 ms	34488 KB	Output is correct
15	Correct	726 ms	35512 KB	Output is correct
16	Correct	622 ms	40264 KB	Output is correct
17	Correct	606 ms	34636 KB	Output is correct
18	Correct	521 ms	36388 KB	Output is correct
19	Correct	568 ms	33460 KB	Output is correct
20	Correct	662 ms	34996 KB	Output is correct
21	Correct	742 ms	35496 KB	Output is correct
22	Correct	708 ms	42884 KB	Output is correct
23	Correct	628 ms	41864 KB	Output is correct
24	Correct	613 ms	41628 KB	Output is correct
25	Correct	786 ms	36484 KB	Output is correct
26	Correct	630 ms	42152 KB	Output is correct
27	Correct	638 ms	35176 KB	Output is correct
28	Correct	511 ms	37516 KB	Output is correct
29	Correct	610 ms	33660 KB	Output is correct
30	Correct	697 ms	42892 KB	Output is correct
31	Correct	676 ms	45964 KB	Output is correct
32	Correct	666 ms	46248 KB	Output is correct
33	Correct	592 ms	34472 KB	Output is correct
34	Correct	613 ms	34440 KB	Output is correct
35	Correct	642 ms	42192 KB	Output is correct
36	Correct	526 ms	33412 KB	Output is correct
37	Correct	661 ms	35460 KB	Output is correct
38	Correct	603 ms	33448 KB	Output is correct
39	Correct	593 ms	34728 KB	Output is correct
40	Correct	568 ms	45292 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	21128 KB	Output is correct
2	Correct	236 ms	21072 KB	Output is correct
3	Correct	234 ms	21072 KB	Output is correct
4	Correct	232 ms	21072 KB	Output is correct
5	Correct	232 ms	21072 KB	Output is correct
6	Correct	229 ms	21088 KB	Output is correct
7	Correct	233 ms	21180 KB	Output is correct
8	Correct	277 ms	21180 KB	Output is correct
9	Correct	247 ms	21072 KB	Output is correct
10	Correct	236 ms	21084 KB	Output is correct
11	Incorrect	281 ms	32404 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	21128 KB	Output is correct
2	Correct	236 ms	21072 KB	Output is correct
3	Correct	234 ms	21072 KB	Output is correct
4	Correct	232 ms	21072 KB	Output is correct
5	Correct	232 ms	21072 KB	Output is correct
6	Correct	229 ms	21088 KB	Output is correct
7	Correct	233 ms	21180 KB	Output is correct
8	Correct	277 ms	21180 KB	Output is correct
9	Correct	247 ms	21072 KB	Output is correct
10	Correct	236 ms	21084 KB	Output is correct
11	Correct	693 ms	35548 KB	Output is correct
12	Correct	725 ms	35184 KB	Output is correct
13	Correct	617 ms	34344 KB	Output is correct
14	Correct	591 ms	34488 KB	Output is correct
15	Correct	726 ms	35512 KB	Output is correct
16	Correct	622 ms	40264 KB	Output is correct
17	Correct	606 ms	34636 KB	Output is correct
18	Correct	521 ms	36388 KB	Output is correct
19	Correct	568 ms	33460 KB	Output is correct
20	Correct	662 ms	34996 KB	Output is correct
21	Correct	742 ms	35496 KB	Output is correct
22	Correct	708 ms	42884 KB	Output is correct
23	Correct	628 ms	41864 KB	Output is correct
24	Correct	613 ms	41628 KB	Output is correct
25	Correct	786 ms	36484 KB	Output is correct
26	Correct	630 ms	42152 KB	Output is correct
27	Correct	638 ms	35176 KB	Output is correct
28	Correct	511 ms	37516 KB	Output is correct
29	Correct	610 ms	33660 KB	Output is correct
30	Correct	697 ms	42892 KB	Output is correct
31	Correct	676 ms	45964 KB	Output is correct
32	Correct	666 ms	46248 KB	Output is correct
33	Correct	592 ms	34472 KB	Output is correct
34	Correct	613 ms	34440 KB	Output is correct
35	Correct	642 ms	42192 KB	Output is correct
36	Correct	526 ms	33412 KB	Output is correct
37	Correct	661 ms	35460 KB	Output is correct
38	Correct	603 ms	33448 KB	Output is correct
39	Correct	593 ms	34728 KB	Output is correct
40	Correct	568 ms	45292 KB	Output is correct
41	Incorrect	281 ms	32404 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #1114787

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