Submission #333121

#	Time	Username	Problem	Language	Result	Execution time	Memory
333121		soroush	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	2 ms	492 KiB

snake_escaping

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll maxn  = 2e6+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int l , q;
int a[maxn];
string s;
 
int ans[maxn];
 
int p[30];

void sub1(){
	for(int i = 0 ; i < p[l] ; i ++){
		int res = 0;
		int x = i;
		for(int j = l ; j >= 0 ; j --){
			if(x >= 2*p[j]){
				x = i;
				x-=2*p[j];
				ans[i] = ans[x] + ans[x + p[j]];
				break;
			}
			if(x >= p[j])
				res += (1 << j);
			x%=p[j];
			if(j == 0)ans[i] = a[res];
		}
	}
	while(q -- ){
		string t;
		cin >> t;
		reverse(t.begin() , t.end());
		int x = 0;
		for(int i = 0 ; i < l ; i ++)
			if(t[i] == '?')x+=p[i]*2;
			else if(t[i] == '1')x+=p[i];
		cout << ans[x] << endl;
	}
	exit(0);
}

vector < string > t;
int res[maxn];

int32_t main(){
    migmig;
    cin >> l >> q;
    cin >> s;
    for(int i = 0 ; i < (1 << l) ; i ++)
		a[i] = s[i] - '0';
	p[0] = 1;
	for(int i = 1 ; i < 16; i ++)
		p[i] = p[i - 1] * 3;
	if(l <= 9)
		sub1();
	t.reserve(q + 1);
	for(int i = 1 ; i <= q ; i ++)
		cin >> t[i] , reverse(t[i].begin() , t[i].end());
	for(int k = 0 ; k < 128 ; k ++){
		for(int i = 0 ; i < p[l] ; i ++){
			int res = 0;
			int x = i;
			for(int j = l ; j >= 0 ; j --){
				if(x >= 2*p[j]){
					x = i;
					x-=2*p[j];
					ans[i] = ans[x] + ans[x + p[j]];
					break;
				}
				if(x >= p[j])
					res += (1 << j);
				x%=p[j];
				if(j == 0)ans[i] = a[res * 128 + k];
			}
		}
		for(int i = 1 ; i <= q ; i ++){
			bool ok = 1;
			for(int j = 0 ; j < 7 ; j ++){
				if(k&(1 << j)){if(t[i][j] == '0'){ok=0 ;break;}}
				else if(t[i][j] == '1'){ok=0 ;break;}
			}
			if(!ok)continue;
			int x = 0;
			for(int j = 7 ; j < l ; j ++)
				if(t[i][j] == '?')x+=p[i]*2;
				else if(t[i][j] == '1')x+=p[i];
			res[i] += ans[x];
		}
	}
	
	for(int i = 1;  i <= q ; i ++)
		cout << res[i] << endl;
    return(0);
}

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