oj.uz

Submission #1114714

# Submission time Handle Problem Language Result Execution time Memory
1114714 2024-11-19T13:06:05 Z Dan4Life Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 458 ms 19440 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 = 6;
const int B2 = 13-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 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1212 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1212 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct
11 Correct 231 ms 15944 KB Output is correct
12 Correct 241 ms 15432 KB Output is correct
13 Correct 240 ms 14792 KB Output is correct
14 Correct 243 ms 14664 KB Output is correct
15 Correct 244 ms 15952 KB Output is correct
16 Correct 271 ms 14988 KB Output is correct
17 Correct 260 ms 14920 KB Output is correct
18 Correct 205 ms 16932 KB Output is correct
19 Correct 216 ms 13540 KB Output is correct
20 Correct 265 ms 15432 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1212 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct
11 Correct 231 ms 15944 KB Output is correct
12 Correct 241 ms 15432 KB Output is correct
13 Correct 240 ms 14792 KB Output is correct
14 Correct 243 ms 14664 KB Output is correct
15 Correct 244 ms 15952 KB Output is correct
16 Correct 271 ms 14988 KB Output is correct
17 Correct 260 ms 14920 KB Output is correct
18 Correct 205 ms 16932 KB Output is correct
19 Correct 216 ms 13540 KB Output is correct
20 Correct 265 ms 15432 KB Output is correct
21 Incorrect 339 ms 19440 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1212 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct
11 Runtime error 458 ms 8936 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 984 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1276 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1212 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct
11 Correct 231 ms 15944 KB Output is correct
12 Correct 241 ms 15432 KB Output is correct
13 Correct 240 ms 14792 KB Output is correct
14 Correct 243 ms 14664 KB Output is correct
15 Correct 244 ms 15952 KB Output is correct
16 Correct 271 ms 14988 KB Output is correct
17 Correct 260 ms 14920 KB Output is correct
18 Correct 205 ms 16932 KB Output is correct
19 Correct 216 ms 13540 KB Output is correct
20 Correct 265 ms 15432 KB Output is correct
21 Incorrect 339 ms 19440 KB Output isn't correct
22 Halted 0 ms 0 KB -