Submission #966304

#	Time	Username	Problem	Language	Result	Execution time	Memory
966304		8pete8	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1040 ms	21748 KiB

snake_escaping

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
#define double long double
const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int dp1[Mxn+10],cost[Mxn+10],rdp0[Mxn+10];
int32_t main(){
	fastio
	int n,q;cin>>n>>q;
	string a;cin>>a;
	auto change=[&](int x){
		int k=0;
		for(int i=0;i<n;i++)if(!(x&(1LL<<i)))k+=1LL<<i;
		return k;
	};
	for(int i=0;i<(1LL<<n);i++)cost[i]=dp1[i]=rdp0[change(i)]=(a[i]-'0');
	for(int i=0;i<n;i++)for(int j=0;j<(1LL<<n);j++)if(j&(1LL<<i))dp1[j]+=dp1[j^(1LL<<i)];
	//for(int i=0;i<n;i++)for(int j=(1LL<<n)-1;j>=0;j--)if(!(j&(1LL<<i)))dp0[j]+=dp0[j+(1LL<<i)];
	int root=sqrt(n);
	root++;
	for(int i=0;i<n;i++)for(int j=0;j<(1LL<<n);j++)if(j&(1LL<<i))rdp0[j]+=rdp0[j^(1LL<<i)];
	while(q--){
		cin>>a;
		reverse(all(a));
		int x=0,y=0;
		vector<int>c;
		int bro=0,bro2=0,c1=0,c0=0;
		for(int i=0;i<n;i++){
			if(a[i]=='1')x+=(1LL<<i),y+=(1LL<<i),c1++;
			else if(a[i]=='?')c.pb(i),bro+=(1LL<<i),x+=(1LL<<i);
			else c0++;
		}
		int m=0;
		int ans=0,g;
		if(c.size()<=root){//5 tl
			m=c.size();
			for(int i=0;i<(1LL<<m);i++){
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x-=(1LL<<c[j]);
				ans+=cost[x];
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x+=(1LL<<c[j]);
			}
		}
		else if(c1<c0){
			m=c1;
			x-=bro;
			g=x;
			while(1){
				if((m-__builtin_popcount(g))%2)ans-=dp1[g+bro];
				else ans+=dp1[g+bro];
				if(g==0)break;
				g=(g-1)&x;
			}
		}
		else{
			m=c0;
			y=change(y);
			y-=bro;
			int g=y;
			while(1){
				if((m-__builtin_popcount(g))%2)ans-=rdp0[g+bro];
				else ans+=rdp0[g+bro];
				if(g==0)break;
				g=(g-1)&y;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
/*
if cnt? <= sqrt(m) we can do (2^4)? bruteforce (maybe even 5)
else we can do sos dp and somehow remove the overcount
we can turn all ? into one and get sos of that bit
overcount when "1" bit that is originaly turned on switch to 0(for subset)
we can switch them off and subtract from the original answer so it cost 2^(cnt1){
	we need to somehow do pie
	starting from original answer-> if we turn off 1 bit
	ans-(turn of x bit)-(turn of y bit)+(turn of x and y bit)
	so if cnt%2==1 then we subtract
	else we add back in
}
cnt1 can be at most 16,worst case is all 1 (2^16)
we can also do sos dp where 0 is now the "switchable" value
so if cnt0<cnt1 we take do from 0 dp else from 1
tc-> worst case q*(2^m)*m
pre com time is m*(2^m+1)
q*(x*(2^x)+(2^(m-x)/2))
*/

Compilation message (stderr)

snake_escaping.cpp:38:45: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   38 | const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
      |                                             ^~~~
snake_escaping.cpp:38:55: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   38 | const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
      |                                                       ^~~~~
snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:68:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |   if(c.size()<=root){//5 tl
      |      ~~~~~~~~^~~~~~
snake_escaping.cpp:60:13: warning: unused variable 'bro2' [-Wunused-variable]
   60 |   int bro=0,bro2=0,c1=0,c0=0;
      |             ^~~~

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