제출 #41283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41283		Kerim	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	337 ms	65536 KiB

snake_escaping

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx") 
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
#define BLOK 13
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,q;
const int N=(1<<20)+5;
const int M=1594330;
int arr[N];
int dp[N*2],pw[22],ans[N];
char s[N],t[22];
vector<PII>adj[22];
bitset<N>ok[130];
int link[N];
int two[M];
bool vis[M];
void rec(int pos,int mask,int bit,int last){
	if(pos==min(n,BLOK)){
		adj[bit].pb(mp(mask,last));
		return;
	}
	rec(pos+1,mask*3,bit,last);
	rec(pos+1,mask*3+1,bit,last);
	rec(pos+1,mask*3+2,bit+1,min(n,BLOK)-pos-1);
}
//~ int two(int x){
	//~ int bit=0,res=0;
	//~ while(x>=1){
		//~ assert(x%3<2);
		//~ if(x%3)
			//~ res+=(1<<bit);
		//~ x/=3;bit++;
	//~ }
	//~ return res;
//~ }
void f(int l,int r,int mask,int ind){
	if(l==r){
		ok[mask][ind]=1;
		//~ query[mask].pb(mp(suf,ind));
		return;
	}
	if(t[l]=='0')
		f(l+1,r,mask*2,ind);
	if(t[l]=='1')
		f(l+1,r,mask*2+1,ind);
	if(t[l]=='?'){
		f(l+1,r,mask*2,ind);
		f(l+1,r,mask*2+1,ind);
	}	
}
void pre(int pos,int uc,int iki){
	if(pos==13){
		two[uc]=iki;
		return;
	}
	for(int i=0;i<3;i++)
		pre(pos+1,uc*3+i,iki*2+i);
}
int main(){
    //~ freopen("file.in", "r", stdin);
    pre(0,0,0);
    scanf("%d%d",&n,&q);
    scanf("%s",s);
    pw[0]=1;
    for(int i=1;i<=BLOK;i++)
		pw[i]=pw[i-1]*3;
    if(n<=BLOK){
		rec(0,0,0,-1);
		tr(it,adj[0])
			dp[it->ff]=s[two[it->ff]]-'0';
		for(int j=1;j<=n;j++)
			tr(it,adj[j])
				dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
		for(int i=1;i<=q;i++){
			scanf("%s",t);
			int base=0;
			for(int j=0;j<n;j++){
				base=base*3;
				if(t[j]=='1')
					base++;
				if(t[j]=='?')
					base+=2;
			}
			printf("%d\n",dp[base]);
		}
	}
	else{
		rec(0,0,0,-1);
		for(int i=1;i<=q;i++){
			scanf("%s",t);
			int tmp=0;
			for(int j=0;j<n;j++){
				tmp*=3;
				if(t[j]=='1')
					tmp++;
				if(t[j]=='?')
					tmp+=2;
			}
			if(vis[tmp]){
				link[i]=vis[tmp];
				continue;
			}
			vis[tmp]=1;
			int base=0;
			for(int j=n-BLOK;j<n;j++){
				base=base*3;
				if(t[j]=='1')
					base++;
				if(t[j]=='?')
					base+=2;
			}
			f(0,n-BLOK,0,i);arr[i]=base;
		}
		int lek=(1<<BLOK);
		for(int mask=0;mask<(1<<(n-BLOK));mask++){
			tr(it,adj[0])
				dp[it->ff]=s[lek*mask+two[it->ff]]-'0';
			for(int i=1;i<=BLOK;i++)
				tr(it,adj[i])
					dp[it->ff]=dp[it->ff-pw[it->ss]]+dp[it->ff-2*pw[it->ss]];
			for(int i=1;i<=q;i++)
				if(!link[i] and ok[mask][i])
					ans[i]+=dp[arr[i]];
		}
		for(int i=1;i<=q;i++){
			if(!link[i])
				printf("%d\n",ans[i]);
			else	
				printf("%d\n",ans[link[i]]);
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:83:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
                        ^
snake_escaping.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s);
                  ^
snake_escaping.cpp:96:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s",t);
                 ^
snake_escaping.cpp:111:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s",t);
                 ^

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