oj.uz

Submission #1114716

# Submission time Handle Problem Language Result Execution time Memory
1114716 2024-11-19T13:10:39 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 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)

string s;
int n, l, q;
const int p3[] = {1,3,9,27,81,243,729};
const int B1 = 5;
const int B2 = 21-B1;
const int N = p3[B1];
int pre[N][1<<B2], 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;
	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; 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 t = mask2; ; t--,t&=mask2){
			pre[mask1][t]+=sc; if(!t) break;
		}
	}
	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++){
			pre[mask2][i]+=pre[mask1][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); ans = pre[x][0];
			for(int mask = 1; 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 7 ms 56912 KB Output is correct
2 Correct 6 ms 56912 KB Output is correct
3 Correct 6 ms 52984 KB Output is correct
4 Correct 7 ms 54864 KB Output is correct
5 Correct 6 ms 52816 KB Output is correct
6 Correct 6 ms 48976 KB Output is correct
7 Correct 6 ms 48976 KB Output is correct
8 Correct 6 ms 51024 KB Output is correct
9 Correct 6 ms 48976 KB Output is correct
10 Correct 6 ms 46928 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 56912 KB Output is correct
2 Correct 6 ms 56912 KB Output is correct
3 Correct 6 ms 52984 KB Output is correct
4 Correct 7 ms 54864 KB Output is correct
5 Correct 6 ms 52816 KB Output is correct
6 Correct 6 ms 48976 KB Output is correct
7 Correct 6 ms 48976 KB Output is correct
8 Correct 6 ms 51024 KB Output is correct
9 Correct 6 ms 48976 KB Output is correct
10 Correct 6 ms 46928 KB Output is correct
11 Correct 264 ms 51032 KB Output is correct
12 Correct 269 ms 52544 KB Output is correct
13 Correct 255 ms 51784 KB Output is correct
14 Correct 267 ms 51784 KB Output is correct
15 Correct 296 ms 52920 KB Output is correct
16 Correct 261 ms 50076 KB Output is correct
17 Correct 280 ms 48040 KB Output is correct
18 Correct 357 ms 53832 KB Output is correct
19 Correct 234 ms 46920 KB Output is correct
20 Correct 265 ms 38472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 56912 KB Output is correct
2 Correct 6 ms 56912 KB Output is correct
3 Correct 6 ms 52984 KB Output is correct
4 Correct 7 ms 54864 KB Output is correct
5 Correct 6 ms 52816 KB Output is correct
6 Correct 6 ms 48976 KB Output is correct
7 Correct 6 ms 48976 KB Output is correct
8 Correct 6 ms 51024 KB Output is correct
9 Correct 6 ms 48976 KB Output is correct
10 Correct 6 ms 46928 KB Output is correct
11 Correct 264 ms 51032 KB Output is correct
12 Correct 269 ms 52544 KB Output is correct
13 Correct 255 ms 51784 KB Output is correct
14 Correct 267 ms 51784 KB Output is correct
15 Correct 296 ms 52920 KB Output is correct
16 Correct 261 ms 50076 KB Output is correct
17 Correct 280 ms 48040 KB Output is correct
18 Correct 357 ms 53832 KB Output is correct
19 Correct 234 ms 46920 KB Output is correct
20 Correct 265 ms 38472 KB Output is correct
21 Correct 458 ms 10568 KB Output is correct
22 Correct 544 ms 6728 KB Output is correct
23 Correct 330 ms 49992 KB Output is correct
24 Correct 358 ms 29768 KB Output is correct
25 Correct 634 ms 15680 KB Output is correct
26 Correct 388 ms 38264 KB Output is correct
27 Correct 402 ms 38276 KB Output is correct
28 Execution timed out 2039 ms 24816 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 56912 KB Output is correct
2 Correct 6 ms 56912 KB Output is correct
3 Correct 6 ms 52984 KB Output is correct
4 Correct 7 ms 54864 KB Output is correct
5 Correct 6 ms 52816 KB Output is correct
6 Correct 6 ms 48976 KB Output is correct
7 Correct 6 ms 48976 KB Output is correct
8 Correct 6 ms 51024 KB Output is correct
9 Correct 6 ms 48976 KB Output is correct
10 Correct 6 ms 46928 KB Output is correct
11 Runtime error 579 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 56912 KB Output is correct
2 Correct 6 ms 56912 KB Output is correct
3 Correct 6 ms 52984 KB Output is correct
4 Correct 7 ms 54864 KB Output is correct
5 Correct 6 ms 52816 KB Output is correct
6 Correct 6 ms 48976 KB Output is correct
7 Correct 6 ms 48976 KB Output is correct
8 Correct 6 ms 51024 KB Output is correct
9 Correct 6 ms 48976 KB Output is correct
10 Correct 6 ms 46928 KB Output is correct
11 Correct 264 ms 51032 KB Output is correct
12 Correct 269 ms 52544 KB Output is correct
13 Correct 255 ms 51784 KB Output is correct
14 Correct 267 ms 51784 KB Output is correct
15 Correct 296 ms 52920 KB Output is correct
16 Correct 261 ms 50076 KB Output is correct
17 Correct 280 ms 48040 KB Output is correct
18 Correct 357 ms 53832 KB Output is correct
19 Correct 234 ms 46920 KB Output is correct
20 Correct 265 ms 38472 KB Output is correct
21 Correct 458 ms 10568 KB Output is correct
22 Correct 544 ms 6728 KB Output is correct
23 Correct 330 ms 49992 KB Output is correct
24 Correct 358 ms 29768 KB Output is correct
25 Correct 634 ms 15680 KB Output is correct
26 Correct 388 ms 38264 KB Output is correct
27 Correct 402 ms 38276 KB Output is correct
28 Execution timed out 2039 ms 24816 KB Time limit exceeded
29 Halted 0 ms 0 KB -