제출 #122507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122507		egorlifar	Snake Escaping (JOI18_snake_escaping)	C++17	5 / 100	633 ms	65536 KiB

snake_escaping

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";


int l, q;
string s;
char c[1 << 20];
vector<char> st[1000228];
int ans[1594329];
int who[1000228];
int dp[1594329];
int pos[1594329];
int g[30];
bool bad[1594329];
int prefs[1594329];


long long get(string s) {
	int it = 0;
	long long res = 0;
	for (auto x: s) {

		if (x == '?') {
			res += g[it] * 2;
		} else {
			res += g[it] * (x - '0');
		}
		it++;
	}
	return res;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> l >> q;
	cin >> s;
	for (int i = 0; i < (1 << l); i++) {
		c[i] = s[i] - '0';
	}
	int t = 1;
	for (int i = 0; i < l - 7; i++) {
		t *= 3;
	}
		g[0] = 1;
	for (int i = 1; i <= 20; i++) {
		g[i] = g[i - 1] * 3;
	}
	if (l <= 7) {
		t = 1;
		for (int i = 0; i < l; i++) {
			t *= 3;
		}
		for (int mask = 0; mask < t; mask++) {
	        int id = mask;
	        bool was = false;
	        int cur = 0;
	        int r = 0;
	        int cur1 = 0;
	        int g = 1;
	        for (int t = 0; t < l; t++) {
	            int s = id % 3;
	            if (was) {
	                cur += s * g;
	                cur1 += s * g;
	            } else {
	                if (s == 2) {
	                    was = true;
	                    cur += 0 * g;
	                    cur1 += 1 * g;
	                } else {
	                    cur += s * g;
	                    cur1 += s * g;
	                    if (s) {
	                        r += (1 << (l - t - 1));
	                    }
	                }
	            }
	            id /= 3;
	            g *= 3;
	        }
	        if (!was) {
	            ans[mask] = c[r];
	        } else {
	            ans[mask] = ans[cur] + ans[cur1];
	        }
	    }
	    for (int it = 0; it < q; it++) {
	    	string k;
	    	cin >> k;
	        int x = get(k);
	      //  cout << "opa" << endl;
	        cout << ans[x] << '\n';
	    }   
	    return 0;
	}
	
	for (int it = 0; it < q; it++) {
		string f;
		cin >> f;
		long long x;
		x = get(f);
		for (int i = 0; i < l; i++) {
			st[it].pb(x % 3);
		//	cout << (int)st[it].back() << '\n';
			x /= 3;
		}
		reverse(all(st[it]));
		int cur = 1;
		for (int i = 7; i < l; i++) {
			who[it] += (int)st[it][i] * cur;
			cur *= 3;
		}
		for (int i = 0; i < 7; i++) {
			prefs[it] += (int)st[it][i] * g[i];
		}
	}	
	for (int i = 0; i < l - 7; i++) {
		for (int pre = 0; pre < (1 << i); pre++) {
			int rpre = 0;
			for (int k = 0; k < i; k++) {
				if (pre & (1 << k)) {
					rpre += g[k];
				}
			}
			for (int suff = 0; suff < g[l - 7 - i - 1]; suff++) {
				pos[rpre + 2 * g[i] + suff * g[i + 1]] = i + 1;
			}
		}
	}
	for (int mask = 0; mask < 128; mask++) {
		for (int i = 0; i < t; i++) {
			if (pos[i] == 0) {
				int curi = i;
				int nmask = mask;
				for (int j = 0; j < l - 7; j++) {
					int g = curi % 3;
					if (g) {
						nmask += 1 << (7 + j);
					}
					curi /= 3;
				}
				dp[i] = c[nmask];
			} else {
				dp[i] =dp[i - g[pos[i] - 1]] + dp[i - (g[pos[i] - 1] << 1)];
			}
		}
		for (int j = 0; j < g[7]; j++) {
			bad[j] = false;
			int cur = j;
			for (int f = 0; f < 7; f++) {
				int a = cur % 3;
				if (a != 2) {
					bool fs = ((mask & (1 << f)) != 0);
					if (fs != a) {
						bad[j] = true;
						break;
					}
				}
				cur /= 3;
			}
		}
		for (int it = 0; it < q; it++) {
            if (!bad[prefs[it]]) {
                ans[it] += dp[who[it]];
            }
		}
	}
	for (int it = 0; it < q; it++) {
		cout << ans[it] << '\n';
	}
	return 0; 		
}

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