oj.uz

Submission #1115148

# Submission time Handle Problem Language Result Execution time Memory
1115148 2024-11-20T07:10:15 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 537 ms 34900 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)
 
string s;
int n, l, q;
const int p3[] = {1,3,9,27,81,243,729};
const int B1 = 5;
const int B2 = 20-B1;
const int N = p3[B1];
int score[N][1<<B2];
 
int calc(string lol){
	int p = 1, ans = 0, xd;
	for(int i = 0; i < B1; 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; n = (1<<l);
	if(l<=B1){
		for(int _ = 0; _ < q; _++){
			string t; cin >> t; 
			reverse(all(t));
			int cnt = 0;
			for(int i = 0; i < n; i++){
				int ok = 1;
				for(int j = 0; j < l; j++) 
					ok&=(t[j]=='?' or (t[j]-'0')==(i>>j&1));
				cnt+=ok*(s[i]-'0');
			}
			cout << cnt << "\n";
		}
		return 0;
	}
	l-=B1;
	for(int mask = 0; mask < n; mask++){
		int mask1 = calc(mask&((1<<B1)-1));
		int mask2 = mask>>B1;
		int sc = s[mask]-'0';
		score[mask1][mask2]+=sc;
	}
	for(int mask = 0; mask < (1<<(B1*2)); mask++){
		string t = "", t2 = "";
		for(int i = 0; i < B1*2; i+=2){
			int cur = mask>>i&1;
			t+=(char)(cur+'0');
			if(mask>>(i+1)&1) cur=2;
			t2+=(char)(cur+'0');
		}
		int mask1 = calc(t);
		int mask2 = calc(t2);
		if(t==t2) continue;
		for(int i = 0; i < (1<<l); i++)
			score[mask2][i]+=score[mask1][i];
	}
	for(int _ = 0; _ < q; _++){
		string t; cin >> t; reverse(all(t));
		int x = calc(t.substr(0,B1));
		t = t.substr(B1);
		int cnt = 0, ans = 0, xd2 = 0; 
		vector<int> pos, pos2; 
		pos.clear(); pos2.clear();
		for(int i = 0; i < sz(t); i++){
			if(t[i]=='?') pos.pb(i),cnt++;
			else{
				pos2.pb(i);
				if(t[i]=='1') xd2+=1<<i;
			}
		}
		if(cnt*2<=B2){
			for(int mask = 0; mask < (1<<cnt); mask++){
				int xd = 0;
				for(int i = 0; i < cnt; i++)
					if(mask>>i&1) xd+=1<<pos[i];
				ans+=score[x][xd+xd2];
			}
		}
		else{
			cnt = sz(pos2);
			for(int mask = 0; mask < (1<<cnt); mask++){
				int num = __builtin_popcount(mask), xd=0;
				for(int i = 0; i < cnt; i++)
					if(mask>>i&1) xd+=(1<<pos2[i])*(t[pos2[i]]=='0');
				ans+=(num%2?-1:1)*score[x][xd];
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 4 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17400 KB Output is correct
6 Correct 3 ms 17232 KB Output is correct
7 Correct 3 ms 17232 KB Output is correct
8 Correct 3 ms 17232 KB Output is correct
9 Correct 4 ms 17340 KB Output is correct
10 Correct 3 ms 17232 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 4 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17400 KB Output is correct
6 Correct 3 ms 17232 KB Output is correct
7 Correct 3 ms 17232 KB Output is correct
8 Correct 3 ms 17232 KB Output is correct
9 Correct 4 ms 17340 KB Output is correct
10 Correct 3 ms 17232 KB Output is correct
11 Correct 286 ms 29324 KB Output is correct
12 Correct 283 ms 31292 KB Output is correct
13 Correct 315 ms 25776 KB Output is correct
14 Correct 285 ms 25160 KB Output is correct
15 Correct 305 ms 24392 KB Output is correct
16 Correct 292 ms 28900 KB Output is correct
17 Correct 284 ms 23088 KB Output is correct
18 Correct 331 ms 25116 KB Output is correct
19 Correct 264 ms 24916 KB Output is correct
20 Correct 265 ms 31556 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 4 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17400 KB Output is correct
6 Correct 3 ms 17232 KB Output is correct
7 Correct 3 ms 17232 KB Output is correct
8 Correct 3 ms 17232 KB Output is correct
9 Correct 4 ms 17340 KB Output is correct
10 Correct 3 ms 17232 KB Output is correct
11 Correct 286 ms 29324 KB Output is correct
12 Correct 283 ms 31292 KB Output is correct
13 Correct 315 ms 25776 KB Output is correct
14 Correct 285 ms 25160 KB Output is correct
15 Correct 305 ms 24392 KB Output is correct
16 Correct 292 ms 28900 KB Output is correct
17 Correct 284 ms 23088 KB Output is correct
18 Correct 331 ms 25116 KB Output is correct
19 Correct 264 ms 24916 KB Output is correct
20 Correct 265 ms 31556 KB Output is correct
21 Correct 463 ms 34888 KB Output is correct
22 Incorrect 537 ms 25000 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 4 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17400 KB Output is correct
6 Correct 3 ms 17232 KB Output is correct
7 Correct 3 ms 17232 KB Output is correct
8 Correct 3 ms 17232 KB Output is correct
9 Correct 4 ms 17340 KB Output is correct
10 Correct 3 ms 17232 KB Output is correct
11 Incorrect 142 ms 34900 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17232 KB Output is correct
2 Correct 4 ms 17232 KB Output is correct
3 Correct 4 ms 17232 KB Output is correct
4 Correct 4 ms 17244 KB Output is correct
5 Correct 4 ms 17400 KB Output is correct
6 Correct 3 ms 17232 KB Output is correct
7 Correct 3 ms 17232 KB Output is correct
8 Correct 3 ms 17232 KB Output is correct
9 Correct 4 ms 17340 KB Output is correct
10 Correct 3 ms 17232 KB Output is correct
11 Correct 286 ms 29324 KB Output is correct
12 Correct 283 ms 31292 KB Output is correct
13 Correct 315 ms 25776 KB Output is correct
14 Correct 285 ms 25160 KB Output is correct
15 Correct 305 ms 24392 KB Output is correct
16 Correct 292 ms 28900 KB Output is correct
17 Correct 284 ms 23088 KB Output is correct
18 Correct 331 ms 25116 KB Output is correct
19 Correct 264 ms 24916 KB Output is correct
20 Correct 265 ms 31556 KB Output is correct
21 Correct 463 ms 34888 KB Output is correct
22 Incorrect 537 ms 25000 KB Output isn't correct
23 Halted 0 ms 0 KB -