답안 #1114792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114792	2024-11-19T15:48:48 Z	Dan4Life	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	916 ms	39860 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 = 2190;
const int M2 = 1594325;
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	293 ms	23532 KB	Output is correct
2	Correct	284 ms	23380 KB	Output is correct
3	Correct	292 ms	23368 KB	Output is correct
4	Correct	295 ms	23528 KB	Output is correct
5	Correct	278 ms	23368 KB	Output is correct
6	Correct	269 ms	23368 KB	Output is correct
7	Correct	280 ms	23368 KB	Output is correct
8	Correct	269 ms	23368 KB	Output is correct
9	Correct	272 ms	23372 KB	Output is correct
10	Correct	269 ms	23536 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	23532 KB	Output is correct
2	Correct	284 ms	23380 KB	Output is correct
3	Correct	292 ms	23368 KB	Output is correct
4	Correct	295 ms	23528 KB	Output is correct
5	Correct	278 ms	23368 KB	Output is correct
6	Correct	269 ms	23368 KB	Output is correct
7	Correct	280 ms	23368 KB	Output is correct
8	Correct	269 ms	23368 KB	Output is correct
9	Correct	272 ms	23372 KB	Output is correct
10	Correct	269 ms	23536 KB	Output is correct
11	Correct	692 ms	37756 KB	Output is correct
12	Correct	774 ms	37504 KB	Output is correct
13	Correct	779 ms	36612 KB	Output is correct
14	Correct	783 ms	36872 KB	Output is correct
15	Correct	879 ms	37760 KB	Output is correct
16	Correct	781 ms	37044 KB	Output is correct
17	Correct	809 ms	36984 KB	Output is correct
18	Correct	550 ms	38836 KB	Output is correct
19	Correct	641 ms	35704 KB	Output is correct
20	Correct	726 ms	37556 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	23532 KB	Output is correct
2	Correct	284 ms	23380 KB	Output is correct
3	Correct	292 ms	23368 KB	Output is correct
4	Correct	295 ms	23528 KB	Output is correct
5	Correct	278 ms	23368 KB	Output is correct
6	Correct	269 ms	23368 KB	Output is correct
7	Correct	280 ms	23368 KB	Output is correct
8	Correct	269 ms	23368 KB	Output is correct
9	Correct	272 ms	23372 KB	Output is correct
10	Correct	269 ms	23536 KB	Output is correct
11	Correct	692 ms	37756 KB	Output is correct
12	Correct	774 ms	37504 KB	Output is correct
13	Correct	779 ms	36612 KB	Output is correct
14	Correct	783 ms	36872 KB	Output is correct
15	Correct	879 ms	37760 KB	Output is correct
16	Correct	781 ms	37044 KB	Output is correct
17	Correct	809 ms	36984 KB	Output is correct
18	Correct	550 ms	38836 KB	Output is correct
19	Correct	641 ms	35704 KB	Output is correct
20	Correct	726 ms	37556 KB	Output is correct
21	Correct	760 ms	38044 KB	Output is correct
22	Correct	845 ms	38072 KB	Output is correct
23	Correct	829 ms	37024 KB	Output is correct
24	Correct	799 ms	36764 KB	Output is correct
25	Correct	916 ms	38844 KB	Output is correct
26	Correct	828 ms	37380 KB	Output is correct
27	Correct	763 ms	37380 KB	Output is correct
28	Correct	564 ms	39860 KB	Output is correct
29	Correct	650 ms	35748 KB	Output is correct
30	Correct	786 ms	38152 KB	Output is correct
31	Correct	802 ms	37812 KB	Output is correct
32	Correct	832 ms	37828 KB	Output is correct
33	Correct	753 ms	36784 KB	Output is correct
34	Correct	786 ms	36792 KB	Output is correct
35	Correct	737 ms	37288 KB	Output is correct
36	Correct	556 ms	35748 KB	Output is correct
37	Correct	720 ms	37820 KB	Output is correct
38	Correct	680 ms	35772 KB	Output is correct
39	Correct	759 ms	37048 KB	Output is correct
40	Correct	799 ms	36768 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	23532 KB	Output is correct
2	Correct	284 ms	23380 KB	Output is correct
3	Correct	292 ms	23368 KB	Output is correct
4	Correct	295 ms	23528 KB	Output is correct
5	Correct	278 ms	23368 KB	Output is correct
6	Correct	269 ms	23368 KB	Output is correct
7	Correct	280 ms	23368 KB	Output is correct
8	Correct	269 ms	23368 KB	Output is correct
9	Correct	272 ms	23372 KB	Output is correct
10	Correct	269 ms	23536 KB	Output is correct
11	Incorrect	318 ms	34748 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	23532 KB	Output is correct
2	Correct	284 ms	23380 KB	Output is correct
3	Correct	292 ms	23368 KB	Output is correct
4	Correct	295 ms	23528 KB	Output is correct
5	Correct	278 ms	23368 KB	Output is correct
6	Correct	269 ms	23368 KB	Output is correct
7	Correct	280 ms	23368 KB	Output is correct
8	Correct	269 ms	23368 KB	Output is correct
9	Correct	272 ms	23372 KB	Output is correct
10	Correct	269 ms	23536 KB	Output is correct
11	Correct	692 ms	37756 KB	Output is correct
12	Correct	774 ms	37504 KB	Output is correct
13	Correct	779 ms	36612 KB	Output is correct
14	Correct	783 ms	36872 KB	Output is correct
15	Correct	879 ms	37760 KB	Output is correct
16	Correct	781 ms	37044 KB	Output is correct
17	Correct	809 ms	36984 KB	Output is correct
18	Correct	550 ms	38836 KB	Output is correct
19	Correct	641 ms	35704 KB	Output is correct
20	Correct	726 ms	37556 KB	Output is correct
21	Correct	760 ms	38044 KB	Output is correct
22	Correct	845 ms	38072 KB	Output is correct
23	Correct	829 ms	37024 KB	Output is correct
24	Correct	799 ms	36764 KB	Output is correct
25	Correct	916 ms	38844 KB	Output is correct
26	Correct	828 ms	37380 KB	Output is correct
27	Correct	763 ms	37380 KB	Output is correct
28	Correct	564 ms	39860 KB	Output is correct
29	Correct	650 ms	35748 KB	Output is correct
30	Correct	786 ms	38152 KB	Output is correct
31	Correct	802 ms	37812 KB	Output is correct
32	Correct	832 ms	37828 KB	Output is correct
33	Correct	753 ms	36784 KB	Output is correct
34	Correct	786 ms	36792 KB	Output is correct
35	Correct	737 ms	37288 KB	Output is correct
36	Correct	556 ms	35748 KB	Output is correct
37	Correct	720 ms	37820 KB	Output is correct
38	Correct	680 ms	35772 KB	Output is correct
39	Correct	759 ms	37048 KB	Output is correct
40	Correct	799 ms	36768 KB	Output is correct
41	Incorrect	318 ms	34748 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #1114792

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