oj.uz

Submission #210558

# Submission time Handle Problem Language Result Execution time Memory
210558 2020-03-17T17:08:05 Z kshitij_sodani Snake Escaping (JOI18_snake_escaping) C++17
58 / 100
 1100 ms 65540 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long llo;
#define a first
#define  b second
#define endl "\n"
int aa=7;
int aac[1000001][20];
 
vector<int> pre[130];
int sl3[21];
int sl[22];
int l;
int dp[1600000];//3^13
int last[1600000];//3^13
int ans[1000001];//q
int it[1100001];//n
int num[1100001];//q
int oo[1600000];
int ok;
void find(int ind,int tot,int ind2){//pre_sub
	if(ind==aa){
		pre[tot].pb(ind2);
	//	cout<<tot<<" "<<ind2<<endl;
	}
	else{
		if(aac[ind2][ind]!=1){
			find(ind+1,tot,ind2);
		}
		if(aac[ind2][ind]>0){
			find(ind+1,tot+sl[aa-ind-1],ind2);
		}
	}
}
void find2(int ind,int ind2,int tot=0){//
	if(ind==l-aa){
		last[tot]=ind2;
//		cout<<tot<<","<<ind2<<endl;
		return;
	}
	if(ind==ind2){
		find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]);
	}
	else{
		find2(ind+1,ind2,tot);
		find2(ind+1,ind2,tot+sl3[(l-aa)-ind-1]);
	}
	if(ind<ind2){
		find2(ind+1,ind2,tot+2*sl3[(l-aa)-ind-1]);
	}
}
int find3(int ind){//dp
	if(dp[ind]>-1){
		return dp[ind];
	}
	if(last[ind]==-1){
		dp[ind]=it[oo[ind]+ok*(sl[l-aa])];
		return dp[ind];
	}
	dp[ind]=find3(ind-sl3[l-aa-last[ind]-1])+find3(ind-2*sl3[l-aa-last[ind]-1]);
	return dp[ind];
 
}
void find4(int ind5,int su1=0,int su2=0){
	if(ind5==13){
		oo[su1]=su2;

	}
	else{
		find4(ind5+1,su1,su2);
		find4(ind5+1,su1+sl3[13-ind5-1],su2+sl[13-ind5-1]);
		find4(ind5+1,su1+2*sl3[13-ind5-1],su2);
		
	}
}
//void(int)
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(last,-1,sizeof(last));
	memset(num,0,sizeof(num));
	sl[0]=1;
	for(int i=1;i<22;i++){
		sl[i]=2*sl[i-1];
	}
	sl3[0]=1;
	for(int i=1;i<14;i++){
		sl3[i]=3*sl3[i-1];
	}
 
	int q;
	cin>>l>>q;
		aa=min((int)7,l-1);
	int n=sl[l];
	
	char ss;
	for(int i=0;i<n;i++){
		cin>>ss;
		it[i]=ss-'0';
	}
	
 
	for(int ii=0;ii<q;ii++){
		for(int i=0;i<l;i++){
			cin>>ss;
			if(ss=='0'){
				aac[ii][i]=0;
				if(l==1){
					cout<<it[0]<<endl;
				}	
			}
			else if(ss=='1'){
	
				aac[ii][i]=1;
				if(l==1){
					cout<<it[1]<<endl;
				}
				else{
					if(i>=aa){
						num[ii]+=sl3[l-i-1];
					}
				} 
			}
			else{
				aac[ii][i]=2;
				if(l==1){
					cout<<it[0]+it[1]<<endl;
				}
				else{
					if(i>=aa){
						num[ii]+=2*sl3[l-i-1];
					}
				}
			}
		}
	}
		/*for(int i=0;i<q;i++){
		cout<<num[i]<<" ";
	}
	cout<<endl;*/
	if(l==1){
		return 0;
	}
	for(int i=0;i<q;i++){
		find((int)0,(int)0,i);
	}
	memset(ans,0,sizeof(ans));
	for(int i=0;i<l-aa;i++){
		find2(0,i,0);
	}
/*    for(int j=0;j<1600000;j++){
 
		int jj=j;
		int ind5=0;
		int sp=0;
		while(jj){
			if(jj%3==1){
				sp+=sl[ind5];
			}
			jj/=3;
			ind5+=1;
		}
		oo[j]=sp;
	}*/
	find4(0);
	//cout<<oo[4]<<endl;
	for(int i=0;i<130;i++){
		ok=i;
		if(pre[i].size()){
			memset(dp,(int)-1,sizeof(dp));
			for(auto j:pre[i]){
				//ans[j]+=it[i];
				find3(num[j]);
				ans[j]+=dp[num[j]];
			//	cout<<i<<":"<<j<<":"<<dp[num[j]]<<endl;
 
			}
		}
 
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
 
 
 
 
 
 
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 27512 KB Output is correct
2 Correct 67 ms 27384 KB Output is correct
3 Correct 72 ms 27512 KB Output is correct
4 Correct 74 ms 27512 KB Output is correct
5 Correct 76 ms 27512 KB Output is correct
6 Correct 77 ms 27512 KB Output is correct
7 Correct 75 ms 27512 KB Output is correct
8 Correct 76 ms 27896 KB Output is correct
9 Correct 67 ms 27384 KB Output is correct
10 Correct 72 ms 27512 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 27512 KB Output is correct
2 Correct 67 ms 27384 KB Output is correct
3 Correct 72 ms 27512 KB Output is correct
4 Correct 74 ms 27512 KB Output is correct
5 Correct 76 ms 27512 KB Output is correct
6 Correct 77 ms 27512 KB Output is correct
7 Correct 75 ms 27512 KB Output is correct
8 Correct 76 ms 27896 KB Output is correct
9 Correct 67 ms 27384 KB Output is correct
10 Correct 72 ms 27512 KB Output is correct
11 Runtime error 223 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 27512 KB Output is correct
2 Correct 67 ms 27384 KB Output is correct
3 Correct 72 ms 27512 KB Output is correct
4 Correct 74 ms 27512 KB Output is correct
5 Correct 76 ms 27512 KB Output is correct
6 Correct 77 ms 27512 KB Output is correct
7 Correct 75 ms 27512 KB Output is correct
8 Correct 76 ms 27896 KB Output is correct
9 Correct 67 ms 27384 KB Output is correct
10 Correct 72 ms 27512 KB Output is correct
11 Runtime error 223 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 27512 KB Output is correct
2 Correct 67 ms 27384 KB Output is correct
3 Correct 72 ms 27512 KB Output is correct
4 Correct 74 ms 27512 KB Output is correct
5 Correct 76 ms 27512 KB Output is correct
6 Correct 77 ms 27512 KB Output is correct
7 Correct 75 ms 27512 KB Output is correct
8 Correct 76 ms 27896 KB Output is correct
9 Correct 67 ms 27384 KB Output is correct
10 Correct 72 ms 27512 KB Output is correct
11 Correct 277 ms 39516 KB Output is correct
12 Correct 380 ms 40056 KB Output is correct
13 Correct 268 ms 36856 KB Output is correct
14 Correct 403 ms 37624 KB Output is correct
15 Correct 1100 ms 43384 KB Output is correct
16 Correct 510 ms 37752 KB Output is correct
17 Correct 519 ms 37752 KB Output is correct
18 Correct 314 ms 63288 KB Output is correct
19 Correct 148 ms 35704 KB Output is correct
20 Correct 373 ms 39796 KB Output is correct
21 Correct 855 ms 39800 KB Output is correct
22 Correct 412 ms 37624 KB Output is correct
23 Correct 169 ms 36344 KB Output is correct
24 Correct 342 ms 37620 KB Output is correct
25 Correct 520 ms 37880 KB Output is correct
26 Correct 85 ms 35832 KB Output is correct
27 Correct 266 ms 39540 KB Output is correct
28 Correct 146 ms 35704 KB Output is correct
29 Correct 260 ms 36856 KB Output is correct
30 Correct 329 ms 37240 KB Output is correct
31 Correct 174 ms 36344 KB Output is correct
32 Correct 493 ms 37756 KB Output is correct
33 Correct 526 ms 37856 KB Output is correct
34 Correct 84 ms 35836 KB Output is correct
35 Correct 559 ms 39544 KB Output is correct
36 Correct 557 ms 39544 KB Output is correct
37 Correct 541 ms 39544 KB Output is correct
38 Correct 542 ms 39544 KB Output is correct
39 Correct 552 ms 39452 KB Output is correct
40 Correct 537 ms 39544 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 27512 KB Output is correct
2 Correct 67 ms 27384 KB Output is correct
3 Correct 72 ms 27512 KB Output is correct
4 Correct 74 ms 27512 KB Output is correct
5 Correct 76 ms 27512 KB Output is correct
6 Correct 77 ms 27512 KB Output is correct
7 Correct 75 ms 27512 KB Output is correct
8 Correct 76 ms 27896 KB Output is correct
9 Correct 67 ms 27384 KB Output is correct
10 Correct 72 ms 27512 KB Output is correct
11 Runtime error 223 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -