oj.uz

Submission #1115143

# Submission time Handle Problem Language Result Execution time Memory
1115143 2024-11-20T06:50:55 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 745 ms 37548 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;
	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-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: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 21084 KB Output is correct
2 Correct 224 ms 21072 KB Output is correct
3 Correct 248 ms 21072 KB Output is correct
4 Correct 221 ms 21248 KB Output is correct
5 Correct 230 ms 21072 KB Output is correct
6 Correct 216 ms 21240 KB Output is correct
7 Correct 208 ms 21072 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 209 ms 21240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 21084 KB Output is correct
2 Correct 224 ms 21072 KB Output is correct
3 Correct 248 ms 21072 KB Output is correct
4 Correct 221 ms 21248 KB Output is correct
5 Correct 230 ms 21072 KB Output is correct
6 Correct 216 ms 21240 KB Output is correct
7 Correct 208 ms 21072 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 209 ms 21240 KB Output is correct
11 Correct 602 ms 35456 KB Output is correct
12 Correct 704 ms 35196 KB Output is correct
13 Correct 594 ms 34428 KB Output is correct
14 Correct 598 ms 34628 KB Output is correct
15 Correct 745 ms 35460 KB Output is correct
16 Correct 613 ms 34688 KB Output is correct
17 Correct 594 ms 34692 KB Output is correct
18 Correct 511 ms 36508 KB Output is correct
19 Correct 620 ms 33460 KB Output is correct
20 Correct 693 ms 35252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 21084 KB Output is correct
2 Correct 224 ms 21072 KB Output is correct
3 Correct 248 ms 21072 KB Output is correct
4 Correct 221 ms 21248 KB Output is correct
5 Correct 230 ms 21072 KB Output is correct
6 Correct 216 ms 21240 KB Output is correct
7 Correct 208 ms 21072 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 209 ms 21240 KB Output is correct
11 Correct 602 ms 35456 KB Output is correct
12 Correct 704 ms 35196 KB Output is correct
13 Correct 594 ms 34428 KB Output is correct
14 Correct 598 ms 34628 KB Output is correct
15 Correct 745 ms 35460 KB Output is correct
16 Correct 613 ms 34688 KB Output is correct
17 Correct 594 ms 34692 KB Output is correct
18 Correct 511 ms 36508 KB Output is correct
19 Correct 620 ms 33460 KB Output is correct
20 Correct 693 ms 35252 KB Output is correct
21 Correct 697 ms 35516 KB Output is correct
22 Correct 712 ms 35752 KB Output is correct
23 Correct 567 ms 34724 KB Output is correct
24 Correct 547 ms 34492 KB Output is correct
25 Correct 738 ms 36536 KB Output is correct
26 Correct 611 ms 35000 KB Output is correct
27 Correct 629 ms 35008 KB Output is correct
28 Correct 508 ms 37548 KB Output is correct
29 Correct 563 ms 33448 KB Output is correct
30 Correct 702 ms 35776 KB Output is correct
31 Correct 669 ms 35480 KB Output is correct
32 Correct 666 ms 35496 KB Output is correct
33 Correct 620 ms 34468 KB Output is correct
34 Correct 622 ms 34500 KB Output is correct
35 Correct 619 ms 35000 KB Output is correct
36 Correct 522 ms 33444 KB Output is correct
37 Correct 642 ms 35520 KB Output is correct
38 Correct 562 ms 33468 KB Output is correct
39 Correct 553 ms 34748 KB Output is correct
40 Correct 555 ms 34488 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 21084 KB Output is correct
2 Correct 224 ms 21072 KB Output is correct
3 Correct 248 ms 21072 KB Output is correct
4 Correct 221 ms 21248 KB Output is correct
5 Correct 230 ms 21072 KB Output is correct
6 Correct 216 ms 21240 KB Output is correct
7 Correct 208 ms 21072 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 209 ms 21240 KB Output is correct
11 Incorrect 269 ms 32488 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 21084 KB Output is correct
2 Correct 224 ms 21072 KB Output is correct
3 Correct 248 ms 21072 KB Output is correct
4 Correct 221 ms 21248 KB Output is correct
5 Correct 230 ms 21072 KB Output is correct
6 Correct 216 ms 21240 KB Output is correct
7 Correct 208 ms 21072 KB Output is correct
8 Correct 224 ms 21228 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 209 ms 21240 KB Output is correct
11 Correct 602 ms 35456 KB Output is correct
12 Correct 704 ms 35196 KB Output is correct
13 Correct 594 ms 34428 KB Output is correct
14 Correct 598 ms 34628 KB Output is correct
15 Correct 745 ms 35460 KB Output is correct
16 Correct 613 ms 34688 KB Output is correct
17 Correct 594 ms 34692 KB Output is correct
18 Correct 511 ms 36508 KB Output is correct
19 Correct 620 ms 33460 KB Output is correct
20 Correct 693 ms 35252 KB Output is correct
21 Correct 697 ms 35516 KB Output is correct
22 Correct 712 ms 35752 KB Output is correct
23 Correct 567 ms 34724 KB Output is correct
24 Correct 547 ms 34492 KB Output is correct
25 Correct 738 ms 36536 KB Output is correct
26 Correct 611 ms 35000 KB Output is correct
27 Correct 629 ms 35008 KB Output is correct
28 Correct 508 ms 37548 KB Output is correct
29 Correct 563 ms 33448 KB Output is correct
30 Correct 702 ms 35776 KB Output is correct
31 Correct 669 ms 35480 KB Output is correct
32 Correct 666 ms 35496 KB Output is correct
33 Correct 620 ms 34468 KB Output is correct
34 Correct 622 ms 34500 KB Output is correct
35 Correct 619 ms 35000 KB Output is correct
36 Correct 522 ms 33444 KB Output is correct
37 Correct 642 ms 35520 KB Output is correct
38 Correct 562 ms 33468 KB Output is correct
39 Correct 553 ms 34748 KB Output is correct
40 Correct 555 ms 34488 KB Output is correct
41 Incorrect 269 ms 32488 KB Output isn't correct
42 Halted 0 ms 0 KB -