답안 #1114790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114790	2024-11-19T15:46:54 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	877 ms	41896 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;
const int N2 = 1<<B2;
const int M1 = 2187;
const int M2 = 1594324;
vector<array<int,2>> v, w[N1];
string s;
bitset<N2> 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 < N2; j++){
			int ok = 1, cur = i, cur2 = j;
			for(int k = 0; k < B2; 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; _++){
		if(!sz(v[_])) continue;
		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	283 ms	23452 KB	Output is correct
2	Correct	290 ms	23448 KB	Output is correct
3	Correct	295 ms	23368 KB	Output is correct
4	Correct	290 ms	23368 KB	Output is correct
5	Correct	303 ms	23372 KB	Output is correct
6	Correct	286 ms	23376 KB	Output is correct
7	Correct	299 ms	23368 KB	Output is correct
8	Correct	301 ms	23528 KB	Output is correct
9	Correct	294 ms	23368 KB	Output is correct
10	Correct	296 ms	23440 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	23452 KB	Output is correct
2	Correct	290 ms	23448 KB	Output is correct
3	Correct	295 ms	23368 KB	Output is correct
4	Correct	290 ms	23368 KB	Output is correct
5	Correct	303 ms	23372 KB	Output is correct
6	Correct	286 ms	23376 KB	Output is correct
7	Correct	299 ms	23368 KB	Output is correct
8	Correct	301 ms	23528 KB	Output is correct
9	Correct	294 ms	23368 KB	Output is correct
10	Correct	296 ms	23440 KB	Output is correct
11	Correct	737 ms	40884 KB	Output is correct
12	Correct	752 ms	37384 KB	Output is correct
13	Correct	693 ms	36732 KB	Output is correct
14	Correct	770 ms	36788 KB	Output is correct
15	Correct	833 ms	37764 KB	Output is correct
16	Correct	838 ms	39944 KB	Output is correct
17	Correct	775 ms	36984 KB	Output is correct
18	Correct	560 ms	38840 KB	Output is correct
19	Correct	661 ms	35844 KB	Output is correct
20	Correct	796 ms	37500 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	23452 KB	Output is correct
2	Correct	290 ms	23448 KB	Output is correct
3	Correct	295 ms	23368 KB	Output is correct
4	Correct	290 ms	23368 KB	Output is correct
5	Correct	303 ms	23372 KB	Output is correct
6	Correct	286 ms	23376 KB	Output is correct
7	Correct	299 ms	23368 KB	Output is correct
8	Correct	301 ms	23528 KB	Output is correct
9	Correct	294 ms	23368 KB	Output is correct
10	Correct	296 ms	23440 KB	Output is correct
11	Correct	737 ms	40884 KB	Output is correct
12	Correct	752 ms	37384 KB	Output is correct
13	Correct	693 ms	36732 KB	Output is correct
14	Correct	770 ms	36788 KB	Output is correct
15	Correct	833 ms	37764 KB	Output is correct
16	Correct	838 ms	39944 KB	Output is correct
17	Correct	775 ms	36984 KB	Output is correct
18	Correct	560 ms	38840 KB	Output is correct
19	Correct	661 ms	35844 KB	Output is correct
20	Correct	796 ms	37500 KB	Output is correct
21	Correct	779 ms	38036 KB	Output is correct
22	Correct	775 ms	41896 KB	Output is correct
23	Correct	751 ms	37032 KB	Output is correct
24	Correct	829 ms	36756 KB	Output is correct
25	Correct	877 ms	38836 KB	Output is correct
26	Correct	793 ms	37288 KB	Output is correct
27	Correct	796 ms	37304 KB	Output is correct
28	Correct	572 ms	39848 KB	Output is correct
29	Correct	710 ms	35776 KB	Output is correct
30	Correct	807 ms	41892 KB	Output is correct
31	Correct	782 ms	37820 KB	Output is correct
32	Correct	783 ms	37900 KB	Output is correct
33	Correct	727 ms	37544 KB	Output is correct
34	Correct	844 ms	36776 KB	Output is correct
35	Correct	763 ms	37260 KB	Output is correct
36	Correct	570 ms	35752 KB	Output is correct
37	Correct	761 ms	37908 KB	Output is correct
38	Correct	623 ms	35740 KB	Output is correct
39	Correct	742 ms	37284 KB	Output is correct
40	Correct	774 ms	36788 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	23452 KB	Output is correct
2	Correct	290 ms	23448 KB	Output is correct
3	Correct	295 ms	23368 KB	Output is correct
4	Correct	290 ms	23368 KB	Output is correct
5	Correct	303 ms	23372 KB	Output is correct
6	Correct	286 ms	23376 KB	Output is correct
7	Correct	299 ms	23368 KB	Output is correct
8	Correct	301 ms	23528 KB	Output is correct
9	Correct	294 ms	23368 KB	Output is correct
10	Correct	296 ms	23440 KB	Output is correct
11	Incorrect	320 ms	34752 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	283 ms	23452 KB	Output is correct
2	Correct	290 ms	23448 KB	Output is correct
3	Correct	295 ms	23368 KB	Output is correct
4	Correct	290 ms	23368 KB	Output is correct
5	Correct	303 ms	23372 KB	Output is correct
6	Correct	286 ms	23376 KB	Output is correct
7	Correct	299 ms	23368 KB	Output is correct
8	Correct	301 ms	23528 KB	Output is correct
9	Correct	294 ms	23368 KB	Output is correct
10	Correct	296 ms	23440 KB	Output is correct
11	Correct	737 ms	40884 KB	Output is correct
12	Correct	752 ms	37384 KB	Output is correct
13	Correct	693 ms	36732 KB	Output is correct
14	Correct	770 ms	36788 KB	Output is correct
15	Correct	833 ms	37764 KB	Output is correct
16	Correct	838 ms	39944 KB	Output is correct
17	Correct	775 ms	36984 KB	Output is correct
18	Correct	560 ms	38840 KB	Output is correct
19	Correct	661 ms	35844 KB	Output is correct
20	Correct	796 ms	37500 KB	Output is correct
21	Correct	779 ms	38036 KB	Output is correct
22	Correct	775 ms	41896 KB	Output is correct
23	Correct	751 ms	37032 KB	Output is correct
24	Correct	829 ms	36756 KB	Output is correct
25	Correct	877 ms	38836 KB	Output is correct
26	Correct	793 ms	37288 KB	Output is correct
27	Correct	796 ms	37304 KB	Output is correct
28	Correct	572 ms	39848 KB	Output is correct
29	Correct	710 ms	35776 KB	Output is correct
30	Correct	807 ms	41892 KB	Output is correct
31	Correct	782 ms	37820 KB	Output is correct
32	Correct	783 ms	37900 KB	Output is correct
33	Correct	727 ms	37544 KB	Output is correct
34	Correct	844 ms	36776 KB	Output is correct
35	Correct	763 ms	37260 KB	Output is correct
36	Correct	570 ms	35752 KB	Output is correct
37	Correct	761 ms	37908 KB	Output is correct
38	Correct	623 ms	35740 KB	Output is correct
39	Correct	742 ms	37284 KB	Output is correct
40	Correct	774 ms	36788 KB	Output is correct
41	Incorrect	320 ms	34752 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #1114790

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