Submission #437224

#	Time	Username	Problem	Language	Result	Execution time	Memory
437224		cpp219	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1608 ms	61496 KiB

snake_escaping

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
ii queries[1000011];
char a[(1<<20)+12];
int ans[1000011];
 
const int N = 1594323;
const int LG = 13;
const int N2 = 2187;
const int LG2 = 7;
 
int dp[N+3];
int nxt[N+3][2];
bitset<(1<<LG2)+1> subbit[N2+3];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i=0;i<N;i++)
	{
		int cur=i; bool pos=0; int t=1;
		for(int j=LG-1;j>=0;j--)
		{
			if(cur%3==2)
			{
				nxt[i][1] = i - t;
				nxt[i][0] = i - t - t;
				pos=1; break;
			}
			cur/=3; t*=3;
		}
		if(!pos)
		{
			nxt[i][0]=nxt[i][1]=-1;
		}
	}
	for(int i=0;i<N2;i++)
	{
		int tmp[LG2+1]={};
		int cur=i;
		for(int j=LG2-1;j>=0;j--)
		{
			tmp[j] = cur%3;
			cur/=3;
		}
		for(int j=0;j<(1<<LG2);j++)
		{
			bool pos=1; int cur2=j;
			for(int k=LG2-1;k>=0;k--)
			{
				int t=cur2&1; cur2>>=1;
				if(tmp[k]==2) continue;
				if(tmp[k]==t) continue;
				pos=0; break;
			}
			if(pos) subbit[i].set(j,1);
		}
	}
	int l,q; cin>>l>>q;
	cin>>a;
	for(int i=0;i<q;i++)
	{
		char x[21]; cin>>x;
		for(int j=0;j<min(l,LG2);j++)
		{
			queries[i].fi*=3;
			queries[i].fi+=(x[j]=='0'?0:(x[j]=='1'?1:2));
		}
		for(int j=LG2;j<l;j++)
		{
			queries[i].se*=3;
			queries[i].se+=(x[j]=='0'?0:(x[j]=='1'?1:2));
		}
	}
	int rhs = max(0, l - LG2);
	for(int i=0;i<(1<<min(l,LG2));i++)
	{
		for(int j=0;j<N;j++)
		{
			if(nxt[j][0]==-1)
			{
				int cur=j; int bit = 0;
				for(int k=0;k<rhs;k++)
				{
					if(cur%3) bit^=(1<<k);
					cur/=3;
				}
				dp[j] = a[(i<<rhs)^bit]-'0';
			}
			else
			{
				dp[j] = dp[nxt[j][0]]+dp[nxt[j][1]];
			}
		}
		for(int j=0;j<q;j++)
		{
			if(subbit[queries[j].fi][i])
			{
				ans[j] += dp[queries[j].se];
			}
		}
	}
	for(int i=0;i<q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

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