oj.uz

Submission #1115145

# Submission time Handle Problem Language Result Execution time Memory
1115145 2024-11-20T07:07:05 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 923 ms 65536 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)+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;
	while(lol){
		int r = lol%2; lol/=2;
		ans+=r*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:57:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   57 |     if(t==2 or t==t2) continue; ok=0; break;
      |     ^~
snake_escaping.cpp:57:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   57 |     if(t==2 or t==t2) continue; ok=0; break;
      |                                 ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21072 KB Output is correct
2 Correct 198 ms 21072 KB Output is correct
3 Correct 194 ms 21244 KB Output is correct
4 Correct 199 ms 21072 KB Output is correct
5 Correct 198 ms 21236 KB Output is correct
6 Correct 193 ms 21232 KB Output is correct
7 Correct 229 ms 21072 KB Output is correct
8 Correct 192 ms 21172 KB Output is correct
9 Correct 208 ms 21084 KB Output is correct
10 Correct 228 ms 21236 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21072 KB Output is correct
2 Correct 198 ms 21072 KB Output is correct
3 Correct 194 ms 21244 KB Output is correct
4 Correct 199 ms 21072 KB Output is correct
5 Correct 198 ms 21236 KB Output is correct
6 Correct 193 ms 21232 KB Output is correct
7 Correct 229 ms 21072 KB Output is correct
8 Correct 192 ms 21172 KB Output is correct
9 Correct 208 ms 21084 KB Output is correct
10 Correct 228 ms 21236 KB Output is correct
11 Correct 644 ms 35456 KB Output is correct
12 Correct 706 ms 35168 KB Output is correct
13 Correct 563 ms 34484 KB Output is correct
14 Correct 552 ms 34432 KB Output is correct
15 Correct 730 ms 35508 KB Output is correct
16 Correct 600 ms 34688 KB Output is correct
17 Correct 650 ms 34740 KB Output is correct
18 Correct 511 ms 36532 KB Output is correct
19 Correct 574 ms 33404 KB Output is correct
20 Correct 676 ms 35252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21072 KB Output is correct
2 Correct 198 ms 21072 KB Output is correct
3 Correct 194 ms 21244 KB Output is correct
4 Correct 199 ms 21072 KB Output is correct
5 Correct 198 ms 21236 KB Output is correct
6 Correct 193 ms 21232 KB Output is correct
7 Correct 229 ms 21072 KB Output is correct
8 Correct 192 ms 21172 KB Output is correct
9 Correct 208 ms 21084 KB Output is correct
10 Correct 228 ms 21236 KB Output is correct
11 Correct 644 ms 35456 KB Output is correct
12 Correct 706 ms 35168 KB Output is correct
13 Correct 563 ms 34484 KB Output is correct
14 Correct 552 ms 34432 KB Output is correct
15 Correct 730 ms 35508 KB Output is correct
16 Correct 600 ms 34688 KB Output is correct
17 Correct 650 ms 34740 KB Output is correct
18 Correct 511 ms 36532 KB Output is correct
19 Correct 574 ms 33404 KB Output is correct
20 Correct 676 ms 35252 KB Output is correct
21 Correct 678 ms 35448 KB Output is correct
22 Correct 673 ms 35728 KB Output is correct
23 Correct 531 ms 34728 KB Output is correct
24 Correct 550 ms 34468 KB Output is correct
25 Correct 744 ms 36540 KB Output is correct
26 Correct 623 ms 35012 KB Output is correct
27 Correct 616 ms 35008 KB Output is correct
28 Correct 518 ms 37544 KB Output is correct
29 Correct 574 ms 33452 KB Output is correct
30 Correct 683 ms 35752 KB Output is correct
31 Correct 642 ms 35752 KB Output is correct
32 Correct 621 ms 35520 KB Output is correct
33 Correct 593 ms 34468 KB Output is correct
34 Correct 573 ms 34468 KB Output is correct
35 Correct 641 ms 34980 KB Output is correct
36 Correct 515 ms 33452 KB Output is correct
37 Correct 653 ms 35492 KB Output is correct
38 Correct 554 ms 33464 KB Output is correct
39 Correct 562 ms 34748 KB Output is correct
40 Correct 558 ms 34472 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21072 KB Output is correct
2 Correct 198 ms 21072 KB Output is correct
3 Correct 194 ms 21244 KB Output is correct
4 Correct 199 ms 21072 KB Output is correct
5 Correct 198 ms 21236 KB Output is correct
6 Correct 193 ms 21232 KB Output is correct
7 Correct 229 ms 21072 KB Output is correct
8 Correct 192 ms 21172 KB Output is correct
9 Correct 208 ms 21084 KB Output is correct
10 Correct 228 ms 21236 KB Output is correct
11 Correct 268 ms 32488 KB Output is correct
12 Correct 266 ms 34536 KB Output is correct
13 Correct 292 ms 34536 KB Output is correct
14 Correct 260 ms 34528 KB Output is correct
15 Correct 277 ms 34620 KB Output is correct
16 Correct 269 ms 34504 KB Output is correct
17 Correct 247 ms 34552 KB Output is correct
18 Correct 241 ms 34816 KB Output is correct
19 Correct 257 ms 34540 KB Output is correct
20 Correct 273 ms 34536 KB Output is correct
21 Correct 260 ms 34536 KB Output is correct
22 Correct 251 ms 34516 KB Output is correct
23 Correct 265 ms 34584 KB Output is correct
24 Correct 261 ms 34596 KB Output is correct
25 Correct 253 ms 34536 KB Output is correct
26 Correct 251 ms 34572 KB Output is correct
27 Correct 269 ms 34536 KB Output is correct
28 Correct 253 ms 34364 KB Output is correct
29 Correct 259 ms 34636 KB Output is correct
30 Correct 258 ms 34532 KB Output is correct
31 Correct 281 ms 34536 KB Output is correct
32 Correct 255 ms 34536 KB Output is correct
33 Correct 262 ms 34552 KB Output is correct
34 Correct 259 ms 34504 KB Output is correct
35 Correct 252 ms 34540 KB Output is correct
36 Correct 271 ms 34620 KB Output is correct
37 Correct 279 ms 34540 KB Output is correct
38 Correct 265 ms 34612 KB Output is correct
39 Correct 267 ms 34536 KB Output is correct
40 Correct 267 ms 34604 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 21072 KB Output is correct
2 Correct 198 ms 21072 KB Output is correct
3 Correct 194 ms 21244 KB Output is correct
4 Correct 199 ms 21072 KB Output is correct
5 Correct 198 ms 21236 KB Output is correct
6 Correct 193 ms 21232 KB Output is correct
7 Correct 229 ms 21072 KB Output is correct
8 Correct 192 ms 21172 KB Output is correct
9 Correct 208 ms 21084 KB Output is correct
10 Correct 228 ms 21236 KB Output is correct
11 Correct 644 ms 35456 KB Output is correct
12 Correct 706 ms 35168 KB Output is correct
13 Correct 563 ms 34484 KB Output is correct
14 Correct 552 ms 34432 KB Output is correct
15 Correct 730 ms 35508 KB Output is correct
16 Correct 600 ms 34688 KB Output is correct
17 Correct 650 ms 34740 KB Output is correct
18 Correct 511 ms 36532 KB Output is correct
19 Correct 574 ms 33404 KB Output is correct
20 Correct 676 ms 35252 KB Output is correct
21 Correct 678 ms 35448 KB Output is correct
22 Correct 673 ms 35728 KB Output is correct
23 Correct 531 ms 34728 KB Output is correct
24 Correct 550 ms 34468 KB Output is correct
25 Correct 744 ms 36540 KB Output is correct
26 Correct 623 ms 35012 KB Output is correct
27 Correct 616 ms 35008 KB Output is correct
28 Correct 518 ms 37544 KB Output is correct
29 Correct 574 ms 33452 KB Output is correct
30 Correct 683 ms 35752 KB Output is correct
31 Correct 642 ms 35752 KB Output is correct
32 Correct 621 ms 35520 KB Output is correct
33 Correct 593 ms 34468 KB Output is correct
34 Correct 573 ms 34468 KB Output is correct
35 Correct 641 ms 34980 KB Output is correct
36 Correct 515 ms 33452 KB Output is correct
37 Correct 653 ms 35492 KB Output is correct
38 Correct 554 ms 33464 KB Output is correct
39 Correct 562 ms 34748 KB Output is correct
40 Correct 558 ms 34472 KB Output is correct
41 Correct 268 ms 32488 KB Output is correct
42 Correct 266 ms 34536 KB Output is correct
43 Correct 292 ms 34536 KB Output is correct
44 Correct 260 ms 34528 KB Output is correct
45 Correct 277 ms 34620 KB Output is correct
46 Correct 269 ms 34504 KB Output is correct
47 Correct 247 ms 34552 KB Output is correct
48 Correct 241 ms 34816 KB Output is correct
49 Correct 257 ms 34540 KB Output is correct
50 Correct 273 ms 34536 KB Output is correct
51 Correct 260 ms 34536 KB Output is correct
52 Correct 251 ms 34516 KB Output is correct
53 Correct 265 ms 34584 KB Output is correct
54 Correct 261 ms 34596 KB Output is correct
55 Correct 253 ms 34536 KB Output is correct
56 Correct 251 ms 34572 KB Output is correct
57 Correct 269 ms 34536 KB Output is correct
58 Correct 253 ms 34364 KB Output is correct
59 Correct 259 ms 34636 KB Output is correct
60 Correct 258 ms 34532 KB Output is correct
61 Correct 281 ms 34536 KB Output is correct
62 Correct 255 ms 34536 KB Output is correct
63 Correct 262 ms 34552 KB Output is correct
64 Correct 259 ms 34504 KB Output is correct
65 Correct 252 ms 34540 KB Output is correct
66 Correct 271 ms 34620 KB Output is correct
67 Correct 279 ms 34540 KB Output is correct
68 Correct 265 ms 34612 KB Output is correct
69 Correct 267 ms 34536 KB Output is correct
70 Correct 267 ms 34604 KB Output is correct
71 Correct 690 ms 65536 KB Output is correct
72 Correct 767 ms 65536 KB Output is correct
73 Correct 673 ms 65536 KB Output is correct
74 Correct 685 ms 65536 KB Output is correct
75 Correct 923 ms 65536 KB Output is correct
76 Correct 759 ms 65536 KB Output is correct
77 Correct 732 ms 65536 KB Output is correct
78 Correct 587 ms 65536 KB Output is correct
79 Correct 689 ms 65536 KB Output is correct
80 Correct 753 ms 65536 KB Output is correct
81 Correct 794 ms 65536 KB Output is correct
82 Correct 707 ms 65536 KB Output is correct
83 Correct 680 ms 65536 KB Output is correct
84 Correct 652 ms 65536 KB Output is correct
85 Correct 645 ms 65536 KB Output is correct
86 Correct 529 ms 65536 KB Output is correct
87 Correct 747 ms 65536 KB Output is correct
88 Correct 681 ms 65536 KB Output is correct
89 Correct 676 ms 65536 KB Output is correct
90 Correct 648 ms 65536 KB Output is correct
91 Correct 658 ms 65536 KB Output is correct
92 Correct 698 ms 65536 KB Output is correct
93 Correct 693 ms 65536 KB Output is correct
94 Correct 578 ms 65536 KB Output is correct
95 Correct 757 ms 65536 KB Output is correct
96 Correct 820 ms 65536 KB Output is correct
97 Correct 750 ms 65536 KB Output is correct
98 Correct 707 ms 65536 KB Output is correct
99 Correct 692 ms 65536 KB Output is correct
100 Correct 715 ms 65536 KB Output is correct