답안 #41283 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41283	2018-02-15T11:41:40 Z	Kerim	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	337 ms	65536 KB

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;
}

Compilation message

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7416 KB	Output is correct
2	Correct	20 ms	7532 KB	Output is correct
3	Correct	17 ms	7616 KB	Output is correct
4	Correct	26 ms	7828 KB	Output is correct
5	Correct	24 ms	7828 KB	Output is correct
6	Correct	17 ms	7828 KB	Output is correct
7	Correct	25 ms	7844 KB	Output is correct
8	Correct	19 ms	7856 KB	Output is correct
9	Correct	17 ms	7868 KB	Output is correct
10	Correct	18 ms	7896 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7416 KB	Output is correct
2	Correct	20 ms	7532 KB	Output is correct
3	Correct	17 ms	7616 KB	Output is correct
4	Correct	26 ms	7828 KB	Output is correct
5	Correct	24 ms	7828 KB	Output is correct
6	Correct	17 ms	7828 KB	Output is correct
7	Correct	25 ms	7844 KB	Output is correct
8	Correct	19 ms	7856 KB	Output is correct
9	Correct	17 ms	7868 KB	Output is correct
10	Correct	18 ms	7896 KB	Output is correct
11	Correct	283 ms	22656 KB	Output is correct
12	Correct	248 ms	32908 KB	Output is correct
13	Correct	278 ms	43072 KB	Output is correct
14	Correct	270 ms	53900 KB	Output is correct
15	Correct	298 ms	65536 KB	Output is correct
16	Correct	304 ms	65536 KB	Output is correct
17	Correct	337 ms	65536 KB	Output is correct
18	Correct	244 ms	65536 KB	Output is correct
19	Correct	277 ms	65536 KB	Output is correct
20	Correct	301 ms	65536 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7416 KB	Output is correct
2	Correct	20 ms	7532 KB	Output is correct
3	Correct	17 ms	7616 KB	Output is correct
4	Correct	26 ms	7828 KB	Output is correct
5	Correct	24 ms	7828 KB	Output is correct
6	Correct	17 ms	7828 KB	Output is correct
7	Correct	25 ms	7844 KB	Output is correct
8	Correct	19 ms	7856 KB	Output is correct
9	Correct	17 ms	7868 KB	Output is correct
10	Correct	18 ms	7896 KB	Output is correct
11	Correct	283 ms	22656 KB	Output is correct
12	Correct	248 ms	32908 KB	Output is correct
13	Correct	278 ms	43072 KB	Output is correct
14	Correct	270 ms	53900 KB	Output is correct
15	Correct	298 ms	65536 KB	Output is correct
16	Correct	304 ms	65536 KB	Output is correct
17	Correct	337 ms	65536 KB	Output is correct
18	Correct	244 ms	65536 KB	Output is correct
19	Correct	277 ms	65536 KB	Output is correct
20	Correct	301 ms	65536 KB	Output is correct
21	Runtime error	71 ms	65536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7416 KB	Output is correct
2	Correct	20 ms	7532 KB	Output is correct
3	Correct	17 ms	7616 KB	Output is correct
4	Correct	26 ms	7828 KB	Output is correct
5	Correct	24 ms	7828 KB	Output is correct
6	Correct	17 ms	7828 KB	Output is correct
7	Correct	25 ms	7844 KB	Output is correct
8	Correct	19 ms	7856 KB	Output is correct
9	Correct	17 ms	7868 KB	Output is correct
10	Correct	18 ms	7896 KB	Output is correct
11	Runtime error	75 ms	65536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7416 KB	Output is correct
2	Correct	20 ms	7532 KB	Output is correct
3	Correct	17 ms	7616 KB	Output is correct
4	Correct	26 ms	7828 KB	Output is correct
5	Correct	24 ms	7828 KB	Output is correct
6	Correct	17 ms	7828 KB	Output is correct
7	Correct	25 ms	7844 KB	Output is correct
8	Correct	19 ms	7856 KB	Output is correct
9	Correct	17 ms	7868 KB	Output is correct
10	Correct	18 ms	7896 KB	Output is correct
11	Correct	283 ms	22656 KB	Output is correct
12	Correct	248 ms	32908 KB	Output is correct
13	Correct	278 ms	43072 KB	Output is correct
14	Correct	270 ms	53900 KB	Output is correct
15	Correct	298 ms	65536 KB	Output is correct
16	Correct	304 ms	65536 KB	Output is correct
17	Correct	337 ms	65536 KB	Output is correct
18	Correct	244 ms	65536 KB	Output is correct
19	Correct	277 ms	65536 KB	Output is correct
20	Correct	301 ms	65536 KB	Output is correct
21	Runtime error	71 ms	65536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

답안 #41283

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0