Submission #943577

#	Time	Username	Problem	Language	Result	Execution time	Memory
943577		guechotjrhh	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	1507 ms	65536 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;
map<string, int> mp;
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;
}
void rec(string s, int i) {
	if (s.size() == n) {
		if (i == -1) {
			mp[s] = str[sti(s)]-'0'; return;
		}
		int u = 0;
		s[i] = '0';
		u = mp[s];
		s[i] = '1';
		u += mp[s];
		s[i] = '?';
		mp[s] = u;

		return;
	}

	rec(s + '0', i);
	rec(s + '1', i);
	rec(s + '?', s.size());
}
void init(int N, int Q, string S) {
	n = N;
	str = S;
	int z = 1; for (int i = 0; i < n; i++) z *= 3;
	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) mp[s] = str[sti(s)]-'0';
		else {
			int u = 0;
			s[ind] = '0';
			u = mp[s];
			s[ind] = '1';
			u += mp[s];
			s[ind] = '?';
			mp[s] = u;
		}
		//cout << i << ' ' << s << ' ' << mp[s] << endl;
	}
}
int query(string A) {
	return mp[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;
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void rec(std::string, int)':
snake_escaping.cpp:33:15: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |  if (s.size() == n) {
      |      ~~~~~~~~~^~~~

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