oj.uz

Submission #66783

# Submission time Handle Problem Language Result Execution time Memory
66783 2018-08-12T10:07:31 Z hamzqq9 Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 296 ms 35448 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000000000
#define MOD 1000000007
#define N 100005
#define MAX 10000006
#define LOG 22
using namespace std;

short int ans[pw(13)][2190];
short int val[pw(20)+3];
short int po3[12];
int l,q,n;
short int res,value;
char s[pw(20)+3];

int get_pos_of_2(int value) {

	int cur=0;

	while(value) {

		if(value%3==2) return cur;

		value/=3;

		cur++;

	}

	return -1;

}

short int get_val(int bas,int son) {

	short int cur=0;

	for(int i=bas;i<=son;i++) {

		cur+=po3[son-i]*(s[i]=='?'?2:(s[i]-'0'));

	}

	return cur;

}

int get_2_rep(int val) {

	int res=0;

	int curpw=1;

	while(val) {

		res+=curpw*(val%3);

		curpw*=2;

		val/=3;

	}

	return res;

}

void back_track(int bit,int val) {

	if(bit==-1) {

		res+=ans[val][value];

		return ;

	}

	if(s[bit]!='?') back_track(bit-1,val+pw(bit)*(s[bit]=='1'));
	else {

		back_track(bit-1,val+pw(bit));
		back_track(bit-1,val);

	}

} 

void pre_calc() {

	for(int i=0;i<2187;i++) {

		int pos=get_pos_of_2(i);

		int temp=-1;

		int va1=-1,va2=-1;

		if(pos==-1) temp=get_2_rep(i);

		for(int j=0;j<pw(13);j++) {

			if(pos==-1) {

				ans[j][i]=val[temp+pw(7)*j];

			}
			else {

				ans[j][i]=ans[j][i-po3[pos]]+ans[j][i-po3[pos]*2];

			}

		}

	}

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d %d",&l,&q);

	po3[0]=1;

	for(int i=1;i<=10;i++) po3[i]=po3[i-1]*3;

	n=pw(l);

	scanf("%s",s);

	for(int i=0;i<n;i++) {

		val[i]=s[i]-'0';

	}

	pre_calc();

	while(q--) {

		scanf("%s",s+20-l);

		for(int i=0;i<20-l;i++) s[i]='0';

		res=0;

		value=get_val(13,19);

		back_track(12,0);

		printf("%d\n",res);

	}

}

Compilation message

snake_escaping.cpp: In function 'void pre_calc()':
snake_escaping.cpp:111:7: warning: unused variable 'va1' [-Wunused-variable]
   int va1=-1,va2=-1;
       ^~~
snake_escaping.cpp:111:14: warning: unused variable 'va2' [-Wunused-variable]
   int va1=-1,va2=-1;
              ^~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&l,&q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s+20-l);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 35448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 35448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 35448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 35448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 35448 KB Output isn't correct
2 Halted 0 ms 0 KB -