답안 #41284 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41284	2018-02-15T11:44:08 Z	Kerim	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	310 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[M],pw[22],ans[N];
char s[N],t[22];
vector<PII>adj[22];
bitset<N>ok[130];
int link[N];
int two[M];
bitset<M>vis;
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	7544 KB	Output is correct
2	Correct	17 ms	7544 KB	Output is correct
3	Correct	18 ms	7736 KB	Output is correct
4	Correct	18 ms	7736 KB	Output is correct
5	Correct	18 ms	7780 KB	Output is correct
6	Correct	18 ms	7780 KB	Output is correct
7	Correct	18 ms	7812 KB	Output is correct
8	Correct	21 ms	7856 KB	Output is correct
9	Correct	18 ms	7868 KB	Output is correct
10	Correct	18 ms	7884 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7544 KB	Output is correct
2	Correct	17 ms	7544 KB	Output is correct
3	Correct	18 ms	7736 KB	Output is correct
4	Correct	18 ms	7736 KB	Output is correct
5	Correct	18 ms	7780 KB	Output is correct
6	Correct	18 ms	7780 KB	Output is correct
7	Correct	18 ms	7812 KB	Output is correct
8	Correct	21 ms	7856 KB	Output is correct
9	Correct	18 ms	7868 KB	Output is correct
10	Correct	18 ms	7884 KB	Output is correct
11	Correct	291 ms	22676 KB	Output is correct
12	Correct	240 ms	32908 KB	Output is correct
13	Correct	281 ms	43128 KB	Output is correct
14	Correct	275 ms	53828 KB	Output is correct
15	Correct	280 ms	65536 KB	Output is correct
16	Correct	309 ms	65536 KB	Output is correct
17	Correct	290 ms	65536 KB	Output is correct
18	Correct	243 ms	65536 KB	Output is correct
19	Correct	273 ms	65536 KB	Output is correct
20	Correct	310 ms	65536 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	7544 KB	Output is correct
2	Correct	17 ms	7544 KB	Output is correct
3	Correct	18 ms	7736 KB	Output is correct
4	Correct	18 ms	7736 KB	Output is correct
5	Correct	18 ms	7780 KB	Output is correct
6	Correct	18 ms	7780 KB	Output is correct
7	Correct	18 ms	7812 KB	Output is correct
8	Correct	21 ms	7856 KB	Output is correct
9	Correct	18 ms	7868 KB	Output is correct
10	Correct	18 ms	7884 KB	Output is correct
11	Correct	291 ms	22676 KB	Output is correct
12	Correct	240 ms	32908 KB	Output is correct
13	Correct	281 ms	43128 KB	Output is correct
14	Correct	275 ms	53828 KB	Output is correct
15	Correct	280 ms	65536 KB	Output is correct
16	Correct	309 ms	65536 KB	Output is correct
17	Correct	290 ms	65536 KB	Output is correct
18	Correct	243 ms	65536 KB	Output is correct
19	Correct	273 ms	65536 KB	Output is correct
20	Correct	310 ms	65536 KB	Output is correct
21	Runtime error	82 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	7544 KB	Output is correct
2	Correct	17 ms	7544 KB	Output is correct
3	Correct	18 ms	7736 KB	Output is correct
4	Correct	18 ms	7736 KB	Output is correct
5	Correct	18 ms	7780 KB	Output is correct
6	Correct	18 ms	7780 KB	Output is correct
7	Correct	18 ms	7812 KB	Output is correct
8	Correct	21 ms	7856 KB	Output is correct
9	Correct	18 ms	7868 KB	Output is correct
10	Correct	18 ms	7884 KB	Output is correct
11	Runtime error	80 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	7544 KB	Output is correct
2	Correct	17 ms	7544 KB	Output is correct
3	Correct	18 ms	7736 KB	Output is correct
4	Correct	18 ms	7736 KB	Output is correct
5	Correct	18 ms	7780 KB	Output is correct
6	Correct	18 ms	7780 KB	Output is correct
7	Correct	18 ms	7812 KB	Output is correct
8	Correct	21 ms	7856 KB	Output is correct
9	Correct	18 ms	7868 KB	Output is correct
10	Correct	18 ms	7884 KB	Output is correct
11	Correct	291 ms	22676 KB	Output is correct
12	Correct	240 ms	32908 KB	Output is correct
13	Correct	281 ms	43128 KB	Output is correct
14	Correct	275 ms	53828 KB	Output is correct
15	Correct	280 ms	65536 KB	Output is correct
16	Correct	309 ms	65536 KB	Output is correct
17	Correct	290 ms	65536 KB	Output is correct
18	Correct	243 ms	65536 KB	Output is correct
19	Correct	273 ms	65536 KB	Output is correct
20	Correct	310 ms	65536 KB	Output is correct
21	Runtime error	82 ms	65536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

답안 #41284

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