Submission #677614

#	Time	Username	Problem	Language	Result	Execution time	Memory
677614		jamezzz	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2015 ms	40240 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn ((1<<20)+5)

int l,q,t[maxn],super[maxn],sub[maxn];
char s[maxn];

int main(){
	sf("%d%d",&l,&q);
	sf(" %s",&s);
	for(int i=0;i<(1<<l);++i){
		t[i]=s[i]-'0';
		sub[i]=super[i]=t[i];
	}
	for(int i=0;i<l;++i){
		for(int j=0;j<(1<<l);++j){
			if(j&(1<<i))sub[j]+=sub[j^(1<<i)];
		}
	}
	for(int i=0;i<l;++i){
		for(int j=(1<<l)-1;j>=0;--j){
			if((j&(1<<i))==0)super[j]+=super[j^(1<<i)];
		}
	}
	while(q--){
		sf(" %s",&s);
		int a=0,b=0,c=0;
		for(int i=0;i<l;++i){
			if(s[i]=='0')++a;
			else if(s[i]=='1')++b;
			else ++c;
		}
		if(c<=6){
			int ans=0;
			for(int i=0;i<(1<<c);++i){
				int num=0;
				int m=i;
				for(int i=0;i<l;++i){
					num<<=1;
					if(s[i]=='1')++num;
					else if(s[i]=='?'){
						num+=m&1;
						m>>=1;
					}
				}
				ans+=t[num];
			}
			pf("%d\n",ans);
		}
		else if(a<=6){
			int ans=0;
			int m=0;
			for(int i=0;i<l;++i){
				if(s[i]=='1')m^=(1<<l-i-1);
			}
			for(int i=0;i<(1<<a);++i){
				int nm=m,t=i,tot=0;
				for(int j=0;j<l;++j){
					if(s[j]=='0'){
						nm^=(t&1)*(1<<l-j-1);
						tot+=t&1;
						t>>=1;
					}
				}
				ans+=super[nm]*(tot%2?-1:1);
			}
			pf("%d\n",ans);
		}
		else{
			int ans=0;
			int m=0;
			for(int i=0;i<l;++i){
				if(s[i]=='?')m^=(1<<l-i-1);
			}
			for(int i=0;i<(1<<b);++i){
				int nm=m,t=i,tot=0;
				for(int j=0;j<l;++j){
					if(s[j]=='1'){
						nm^=(t&1)*(1<<l-j-1);
						tot+=t&1;
						t>>=1;
					}
				}
				ans+=sub[nm]*((b-tot)%2?-1:1);
			}
			pf("%d\n",ans);
		}
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:69:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1048581]' [-Wformat=]
   69 |  sf(" %s",&s);
      |       ~^  ~~
      |        |  |
      |        |  char (*)[1048581]
      |        char*
snake_escaping.cpp:85:9: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1048581]' [-Wformat=]
   85 |   sf(" %s",&s);
      |        ~^  ~~
      |         |  |
      |         |  char (*)[1048581]
      |         char*
snake_escaping.cpp:113:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  113 |     if(s[i]=='1')m^=(1<<l-i-1);
      |                         ~~~^~
snake_escaping.cpp:119:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  119 |       nm^=(t&1)*(1<<l-j-1);
      |                     ~~~^~
snake_escaping.cpp:132:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  132 |     if(s[i]=='?')m^=(1<<l-i-1);
      |                         ~~~^~
snake_escaping.cpp:138:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  138 |       nm^=(t&1)*(1<<l-j-1);
      |                     ~~~^~
snake_escaping.cpp:68:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  sf("%d%d",&l,&q);
      |    ^
snake_escaping.cpp:69:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  sf(" %s",&s);
      |    ^
snake_escaping.cpp:85:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   sf(" %s",&s);
      |     ^

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