Submission #1162928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162928		irmuun	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	163 ms	2588 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int L,Q;
	cin>>L>>Q;
	string s;
	cin>>s;
	int dig[L+5];
	dig[0]=1;
	for(int i=1;i<=L;i++){
		dig[i]=dig[i-1]*3;
	}
	cout<<dig[L]<<endl;
	vector<string>sn;
	for(int i=0;i<(1<<L);i++){
		string x(L,'0');
		for(int j=0;j<L;j++){
			if(i&(1<<j)){
				x[L-j-1]='1';
			}
		}
		sn.pb(x);
	}
	vector<string>que;
	for(int i=0;i<dig[L];i++){
		string x;
		int cur=i;
		for(int j=0;j<L;j++){
			if(cur%3==0) x+='0';
			else if(cur%3==1) x+='1';
			else x+='?';
			cur/=3;
		}
		que.pb(x);
	}
	vector<int>ans((int)que.size());
	for(int i=0;i<(int)que.size();i++){
		for(int j=0;j<sn.size();j++){
			bool ok=true;
			for(int k=0;k<L;k++){
				if(que[i][k]=='?') continue;
				if(que[i][k]!=sn[j][k]){
					ok=false;
					break;
				}
			}
			if(ok){
				ans[i]+=s[j]-'0';
			}
		}
	}
	for(int i=0;i<Q;i++){
		string t;
		cin>>t;
		int idx=0;
		for(int j=0;j<Q;j++){
			if(t[j]=='1') idx+=dig[j];
			if(t[j]=='?') idx+=(dig[j]<<1);
		}
		cout<<ans[idx]<<"\n";
	}
}

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