oj.uz

Submission #1115126

# Submission time Handle Problem Language Result Execution time Memory
1115126 2024-11-20T05:31:35 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 795 ms 50344 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> 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 231 ms 21072 KB Output is correct
2 Correct 232 ms 21160 KB Output is correct
3 Correct 215 ms 21072 KB Output is correct
4 Correct 210 ms 21236 KB Output is correct
5 Correct 213 ms 21244 KB Output is correct
6 Correct 210 ms 21072 KB Output is correct
7 Correct 210 ms 21072 KB Output is correct
8 Correct 210 ms 21072 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 211 ms 21072 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 21072 KB Output is correct
2 Correct 232 ms 21160 KB Output is correct
3 Correct 215 ms 21072 KB Output is correct
4 Correct 210 ms 21236 KB Output is correct
5 Correct 213 ms 21244 KB Output is correct
6 Correct 210 ms 21072 KB Output is correct
7 Correct 210 ms 21072 KB Output is correct
8 Correct 210 ms 21072 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 211 ms 21072 KB Output is correct
11 Correct 624 ms 46136 KB Output is correct
12 Correct 756 ms 45948 KB Output is correct
13 Correct 617 ms 45296 KB Output is correct
14 Correct 620 ms 45176 KB Output is correct
15 Correct 756 ms 46264 KB Output is correct
16 Correct 620 ms 45432 KB Output is correct
17 Correct 597 ms 45504 KB Output is correct
18 Correct 559 ms 47224 KB Output is correct
19 Correct 619 ms 44156 KB Output is correct
20 Correct 675 ms 46028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 21072 KB Output is correct
2 Correct 232 ms 21160 KB Output is correct
3 Correct 215 ms 21072 KB Output is correct
4 Correct 210 ms 21236 KB Output is correct
5 Correct 213 ms 21244 KB Output is correct
6 Correct 210 ms 21072 KB Output is correct
7 Correct 210 ms 21072 KB Output is correct
8 Correct 210 ms 21072 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 211 ms 21072 KB Output is correct
11 Correct 624 ms 46136 KB Output is correct
12 Correct 756 ms 45948 KB Output is correct
13 Correct 617 ms 45296 KB Output is correct
14 Correct 620 ms 45176 KB Output is correct
15 Correct 756 ms 46264 KB Output is correct
16 Correct 620 ms 45432 KB Output is correct
17 Correct 597 ms 45504 KB Output is correct
18 Correct 559 ms 47224 KB Output is correct
19 Correct 619 ms 44156 KB Output is correct
20 Correct 675 ms 46028 KB Output is correct
21 Correct 697 ms 49320 KB Output is correct
22 Correct 661 ms 48932 KB Output is correct
23 Correct 603 ms 48300 KB Output is correct
24 Correct 602 ms 48176 KB Output is correct
25 Correct 795 ms 50236 KB Output is correct
26 Correct 620 ms 48792 KB Output is correct
27 Correct 649 ms 48808 KB Output is correct
28 Correct 574 ms 50344 KB Output is correct
29 Correct 630 ms 47248 KB Output is correct
30 Correct 685 ms 48372 KB Output is correct
31 Correct 625 ms 49148 KB Output is correct
32 Correct 585 ms 49336 KB Output is correct
33 Correct 593 ms 48168 KB Output is correct
34 Correct 578 ms 47712 KB Output is correct
35 Correct 671 ms 48816 KB Output is correct
36 Correct 536 ms 47016 KB Output is correct
37 Correct 681 ms 49196 KB Output is correct
38 Correct 601 ms 47272 KB Output is correct
39 Correct 606 ms 48536 KB Output is correct
40 Correct 642 ms 48296 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 21072 KB Output is correct
2 Correct 232 ms 21160 KB Output is correct
3 Correct 215 ms 21072 KB Output is correct
4 Correct 210 ms 21236 KB Output is correct
5 Correct 213 ms 21244 KB Output is correct
6 Correct 210 ms 21072 KB Output is correct
7 Correct 210 ms 21072 KB Output is correct
8 Correct 210 ms 21072 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 211 ms 21072 KB Output is correct
11 Incorrect 287 ms 34352 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 21072 KB Output is correct
2 Correct 232 ms 21160 KB Output is correct
3 Correct 215 ms 21072 KB Output is correct
4 Correct 210 ms 21236 KB Output is correct
5 Correct 213 ms 21244 KB Output is correct
6 Correct 210 ms 21072 KB Output is correct
7 Correct 210 ms 21072 KB Output is correct
8 Correct 210 ms 21072 KB Output is correct
9 Correct 212 ms 21072 KB Output is correct
10 Correct 211 ms 21072 KB Output is correct
11 Correct 624 ms 46136 KB Output is correct
12 Correct 756 ms 45948 KB Output is correct
13 Correct 617 ms 45296 KB Output is correct
14 Correct 620 ms 45176 KB Output is correct
15 Correct 756 ms 46264 KB Output is correct
16 Correct 620 ms 45432 KB Output is correct
17 Correct 597 ms 45504 KB Output is correct
18 Correct 559 ms 47224 KB Output is correct
19 Correct 619 ms 44156 KB Output is correct
20 Correct 675 ms 46028 KB Output is correct
21 Correct 697 ms 49320 KB Output is correct
22 Correct 661 ms 48932 KB Output is correct
23 Correct 603 ms 48300 KB Output is correct
24 Correct 602 ms 48176 KB Output is correct
25 Correct 795 ms 50236 KB Output is correct
26 Correct 620 ms 48792 KB Output is correct
27 Correct 649 ms 48808 KB Output is correct
28 Correct 574 ms 50344 KB Output is correct
29 Correct 630 ms 47248 KB Output is correct
30 Correct 685 ms 48372 KB Output is correct
31 Correct 625 ms 49148 KB Output is correct
32 Correct 585 ms 49336 KB Output is correct
33 Correct 593 ms 48168 KB Output is correct
34 Correct 578 ms 47712 KB Output is correct
35 Correct 671 ms 48816 KB Output is correct
36 Correct 536 ms 47016 KB Output is correct
37 Correct 681 ms 49196 KB Output is correct
38 Correct 601 ms 47272 KB Output is correct
39 Correct 606 ms 48536 KB Output is correct
40 Correct 642 ms 48296 KB Output is correct
41 Incorrect 287 ms 34352 KB Output isn't correct
42 Halted 0 ms 0 KB -