oj.uz

Submission #1115142

# Submission time Handle Problem Language Result Execution time Memory
1115142 2024-11-20T06:49:36 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 822 ms 45124 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -