Submission #943582

#	Time	Username	Problem	Language	Result	Execution time	Memory
943582		guechotjrhh	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1466 ms	26452 KiB

snake_escaping

#include<iostream>
#include<string>
using namespace std;

#include<map>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define all(x) x.begin(),x.end()
string str;
int n;
vector<int> vc;
string its(int a, int l) {
	string res = "";
	for (int i = 0; i < l; i++) {
		if ((a % 3) == 2) res += '?';
		else res += '0' + a % 3;
		a /= 3;
	}
	reverse(all(res));
	return res;
}
int sti(string s) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		res <<= 1;
		res += s[i] - '0';
	}
	return res;
}
int st3(string s) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		res *= 3;
		if (s[i] == '?') res += 2;
		else res += s[i] - '0';
	}
	return res;
}
void init(int N, int Q, string S) {
	n = N;
	str = S;
	int z = 1; for (int i = 0; i < n; i++) z *= 3;
	vc.resize(z);
	for (int i = 0; i < z; i++) {
		string s = its(i, n);
		int ind = -1;
		for (int j = 0; j < n; j++) if (s[j] == '?') ind = j;
		if (ind == -1) vc[i] = str[sti(s)]-'0';
		else {
			int u = 0;
			s[ind] = '0';
			u = vc[st3(s)];
			s[ind] = '1';
			u += vc[st3(s)];
			vc[i] = u;
		}
		//cout << i << ' ' << s << ' ' << mp[s] << endl;
	}
}
int query(string A) {
	return vc[st3(A)];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q; cin >> N >> Q;
	string S; cin >> S;
	init(N, Q, move(S));
	
	for (int i = 0; i < Q; i++) {
		string A;
		cin >> A;
		cout << query(move(A)) << endl;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25