oj.uz

답안 #210547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210547 2020-03-17T16:46:09 Z kshitij_sodani Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 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]%2==0){
			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,int ind4){//dp
	if(dp[ind]>-1){
		return dp[ind];
	}
	if(last[ind]==-1){
		dp[ind]=it[ind4+ok*(sl[l-aa])];
		return dp[ind];
	}
	dp[ind]=find3(ind-sl3[l-aa-last[ind]-1],ind4-sl[l-aa-last[ind]-1])+find3(ind-2*sl3[l-aa-last[ind]-1],ind4);
	return dp[ind];
 
}
void find4(int ind5,int su1=0,int su2=0){
	if(ind5==l-aa){
		oo[su1]=su2;
	}
	else{
		find4(ind5+1,su1,su2);
		find4(ind5+1,su1+sl3[l-aa-ind5-1],su2+sl[l-aa-ind5-1]);
		find4(ind5+1,su1+2*sl3[l-aa-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,(int)0,sizeof(ans));
	for(int i=0;i<l-aa;i++){
		find2((int)0,i,(int)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);
	for(int i=0;i<130;i++){
		ok=i;
		if(pre[i].size()){
 
			memset(dp,(int)-1,sizeof(dp));
			for(int j=0;j<1600000;j++){
				find3(j,oo[j]);
			}
			for(auto j:pre[i]){
				//ans[j]+=it[i];
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 21240 KB Output is correct
2 Correct 885 ms 21240 KB Output is correct
3 Correct 852 ms 21288 KB Output is correct
4 Correct 953 ms 21240 KB Output is correct
5 Correct 880 ms 21372 KB Output is correct
6 Correct 885 ms 21240 KB Output is correct
7 Correct 876 ms 21240 KB Output is correct
8 Correct 883 ms 21752 KB Output is correct
9 Correct 776 ms 21240 KB Output is correct
10 Correct 936 ms 21368 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 21240 KB Output is correct
2 Correct 885 ms 21240 KB Output is correct
3 Correct 852 ms 21288 KB Output is correct
4 Correct 953 ms 21240 KB Output is correct
5 Correct 880 ms 21372 KB Output is correct
6 Correct 885 ms 21240 KB Output is correct
7 Correct 876 ms 21240 KB Output is correct
8 Correct 883 ms 21752 KB Output is correct
9 Correct 776 ms 21240 KB Output is correct
10 Correct 936 ms 21368 KB Output is correct
11 Runtime error 218 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

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 21240 KB Output is correct
2 Correct 885 ms 21240 KB Output is correct
3 Correct 852 ms 21288 KB Output is correct
4 Correct 953 ms 21240 KB Output is correct
5 Correct 880 ms 21372 KB Output is correct
6 Correct 885 ms 21240 KB Output is correct
7 Correct 876 ms 21240 KB Output is correct
8 Correct 883 ms 21752 KB Output is correct
9 Correct 776 ms 21240 KB Output is correct
10 Correct 936 ms 21368 KB Output is correct
11 Runtime error 218 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 21240 KB Output is correct
2 Correct 885 ms 21240 KB Output is correct
3 Correct 852 ms 21288 KB Output is correct
4 Correct 953 ms 21240 KB Output is correct
5 Correct 880 ms 21372 KB Output is correct
6 Correct 885 ms 21240 KB Output is correct
7 Correct 876 ms 21240 KB Output is correct
8 Correct 883 ms 21752 KB Output is correct
9 Correct 776 ms 21240 KB Output is correct
10 Correct 936 ms 21368 KB Output is correct
11 Execution timed out 2100 ms 41312 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 832 ms 21240 KB Output is correct
2 Correct 885 ms 21240 KB Output is correct
3 Correct 852 ms 21288 KB Output is correct
4 Correct 953 ms 21240 KB Output is correct
5 Correct 880 ms 21372 KB Output is correct
6 Correct 885 ms 21240 KB Output is correct
7 Correct 876 ms 21240 KB Output is correct
8 Correct 883 ms 21752 KB Output is correct
9 Correct 776 ms 21240 KB Output is correct
10 Correct 936 ms 21368 KB Output is correct
11 Runtime error 218 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -