oj.uz

Submission #1114787

# Submission time Handle Problem Language Result Execution time Memory
1114787 2024-11-19T15:40:30 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 786 ms 46248 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 N = 1<<B1;
const int B2 = 13;
const int N2 = 1<<B2;
const int M = 1594324;
vector<array<int,2>> v, w[N];
string s;
int l, q, ans[M], dp[M];
int nx[2][M];
bitset<N> submask[2187];

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 < M; 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 < 2187; i++){
		for(int j = 0; j < N; j++){
			int ok = 1, cur = i, cur2 = j;
			for(int k = 0; k < 7; k++){
				int t = cur%3, t2=cur2%2; cur/=3; cur2/=2;
				if(t==2) continue;
				if(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; _ < N; _++){
		if(!sz(v[_])) continue;
		memset(dp,0,sizeof(dp));
		for(auto [xd,sc] : w[_]) dp[xd]+=sc;
		for(int i = 0; i < M; 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";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21128 KB Output is correct
2 Correct 236 ms 21072 KB Output is correct
3 Correct 234 ms 21072 KB Output is correct
4 Correct 232 ms 21072 KB Output is correct
5 Correct 232 ms 21072 KB Output is correct
6 Correct 229 ms 21088 KB Output is correct
7 Correct 233 ms 21180 KB Output is correct
8 Correct 277 ms 21180 KB Output is correct
9 Correct 247 ms 21072 KB Output is correct
10 Correct 236 ms 21084 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21128 KB Output is correct
2 Correct 236 ms 21072 KB Output is correct
3 Correct 234 ms 21072 KB Output is correct
4 Correct 232 ms 21072 KB Output is correct
5 Correct 232 ms 21072 KB Output is correct
6 Correct 229 ms 21088 KB Output is correct
7 Correct 233 ms 21180 KB Output is correct
8 Correct 277 ms 21180 KB Output is correct
9 Correct 247 ms 21072 KB Output is correct
10 Correct 236 ms 21084 KB Output is correct
11 Correct 693 ms 35548 KB Output is correct
12 Correct 725 ms 35184 KB Output is correct
13 Correct 617 ms 34344 KB Output is correct
14 Correct 591 ms 34488 KB Output is correct
15 Correct 726 ms 35512 KB Output is correct
16 Correct 622 ms 40264 KB Output is correct
17 Correct 606 ms 34636 KB Output is correct
18 Correct 521 ms 36388 KB Output is correct
19 Correct 568 ms 33460 KB Output is correct
20 Correct 662 ms 34996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21128 KB Output is correct
2 Correct 236 ms 21072 KB Output is correct
3 Correct 234 ms 21072 KB Output is correct
4 Correct 232 ms 21072 KB Output is correct
5 Correct 232 ms 21072 KB Output is correct
6 Correct 229 ms 21088 KB Output is correct
7 Correct 233 ms 21180 KB Output is correct
8 Correct 277 ms 21180 KB Output is correct
9 Correct 247 ms 21072 KB Output is correct
10 Correct 236 ms 21084 KB Output is correct
11 Correct 693 ms 35548 KB Output is correct
12 Correct 725 ms 35184 KB Output is correct
13 Correct 617 ms 34344 KB Output is correct
14 Correct 591 ms 34488 KB Output is correct
15 Correct 726 ms 35512 KB Output is correct
16 Correct 622 ms 40264 KB Output is correct
17 Correct 606 ms 34636 KB Output is correct
18 Correct 521 ms 36388 KB Output is correct
19 Correct 568 ms 33460 KB Output is correct
20 Correct 662 ms 34996 KB Output is correct
21 Correct 742 ms 35496 KB Output is correct
22 Correct 708 ms 42884 KB Output is correct
23 Correct 628 ms 41864 KB Output is correct
24 Correct 613 ms 41628 KB Output is correct
25 Correct 786 ms 36484 KB Output is correct
26 Correct 630 ms 42152 KB Output is correct
27 Correct 638 ms 35176 KB Output is correct
28 Correct 511 ms 37516 KB Output is correct
29 Correct 610 ms 33660 KB Output is correct
30 Correct 697 ms 42892 KB Output is correct
31 Correct 676 ms 45964 KB Output is correct
32 Correct 666 ms 46248 KB Output is correct
33 Correct 592 ms 34472 KB Output is correct
34 Correct 613 ms 34440 KB Output is correct
35 Correct 642 ms 42192 KB Output is correct
36 Correct 526 ms 33412 KB Output is correct
37 Correct 661 ms 35460 KB Output is correct
38 Correct 603 ms 33448 KB Output is correct
39 Correct 593 ms 34728 KB Output is correct
40 Correct 568 ms 45292 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21128 KB Output is correct
2 Correct 236 ms 21072 KB Output is correct
3 Correct 234 ms 21072 KB Output is correct
4 Correct 232 ms 21072 KB Output is correct
5 Correct 232 ms 21072 KB Output is correct
6 Correct 229 ms 21088 KB Output is correct
7 Correct 233 ms 21180 KB Output is correct
8 Correct 277 ms 21180 KB Output is correct
9 Correct 247 ms 21072 KB Output is correct
10 Correct 236 ms 21084 KB Output is correct
11 Incorrect 281 ms 32404 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 21128 KB Output is correct
2 Correct 236 ms 21072 KB Output is correct
3 Correct 234 ms 21072 KB Output is correct
4 Correct 232 ms 21072 KB Output is correct
5 Correct 232 ms 21072 KB Output is correct
6 Correct 229 ms 21088 KB Output is correct
7 Correct 233 ms 21180 KB Output is correct
8 Correct 277 ms 21180 KB Output is correct
9 Correct 247 ms 21072 KB Output is correct
10 Correct 236 ms 21084 KB Output is correct
11 Correct 693 ms 35548 KB Output is correct
12 Correct 725 ms 35184 KB Output is correct
13 Correct 617 ms 34344 KB Output is correct
14 Correct 591 ms 34488 KB Output is correct
15 Correct 726 ms 35512 KB Output is correct
16 Correct 622 ms 40264 KB Output is correct
17 Correct 606 ms 34636 KB Output is correct
18 Correct 521 ms 36388 KB Output is correct
19 Correct 568 ms 33460 KB Output is correct
20 Correct 662 ms 34996 KB Output is correct
21 Correct 742 ms 35496 KB Output is correct
22 Correct 708 ms 42884 KB Output is correct
23 Correct 628 ms 41864 KB Output is correct
24 Correct 613 ms 41628 KB Output is correct
25 Correct 786 ms 36484 KB Output is correct
26 Correct 630 ms 42152 KB Output is correct
27 Correct 638 ms 35176 KB Output is correct
28 Correct 511 ms 37516 KB Output is correct
29 Correct 610 ms 33660 KB Output is correct
30 Correct 697 ms 42892 KB Output is correct
31 Correct 676 ms 45964 KB Output is correct
32 Correct 666 ms 46248 KB Output is correct
33 Correct 592 ms 34472 KB Output is correct
34 Correct 613 ms 34440 KB Output is correct
35 Correct 642 ms 42192 KB Output is correct
36 Correct 526 ms 33412 KB Output is correct
37 Correct 661 ms 35460 KB Output is correct
38 Correct 603 ms 33448 KB Output is correct
39 Correct 593 ms 34728 KB Output is correct
40 Correct 568 ms 45292 KB Output is correct
41 Incorrect 281 ms 32404 KB Output isn't correct
42 Halted 0 ms 0 KB -