답안 #66938 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66938	2018-08-12T19:59:19 Z	hamzqq9	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1253 ms	29380 KB

snake_escaping

#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 3005
#define MAX 10000006
#define LOG 22
#define L 7
#define R 13
using namespace std;
 
int n,q,l;
int cnt[1594325],ans[pw(20)+5];
int po3[20],po2[25],pos[1594325];
char val[pw(20)+5],s[pw(20)+5];
bool oops[1594325],inc[2188][129];
int Right[pw(20)+5];
short Left[pw(20)+5]; 

void do_dp(int value) {
 
	for(int i=0;i<1594323;i++) {
 
		if(oops[i]) cnt[i]=val[value*po2[R]+pos[i]];
		else cnt[i]=cnt[i-po3[pos[i]]]+cnt[i-2*po3[pos[i]]];
 
	}
 
}

int lval,rval;

void back_track(int bit) {

	if(bit==L) {

		inc[rval][lval]=true;

		return ;

	}

	// 1 1 1 ? 
	// 0 0 0 ?

	lval+=po2[bit];

	rval+=po3[bit];

	back_track(bit+1);

	rval+=po3[bit];

	back_track(bit+1);

	lval-=po2[bit];

	back_track(bit+1);

	rval-=po3[bit]*2;

	back_track(bit+1);

}

void pre_cal() {

	oops[0]=oops[1]=true;
	pos[1]=1;

	for(int i=3;i<1594323;i++) {
 
 		if(i%3==2) pos[i]=0;
 		else {

 			int val=i/3;

 			if(oops[val]) {

 				oops[i]=true;
 				pos[i]=pos[val]*2+i%3;

 			}
 			else {

 				pos[i]=pos[val]+1;

 			}

 		}
 
	}

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

		inc[i][0]=inc[i][1]=inc[i][2]=true;

		if(i%3==1) inc[i][0]=false;
		else if(i%3==0) inc[i][1]=false;

		for(int j=3;j<128;j++) {

			if(i%3!=j%2 && i%3!=2) inc[i][j]=0;
			else inc[i][j]=inc[i/3][j/2]; 

		}

	}

//	back_track(0);
 
}
 
int get_value(int bas,int son) {
 
	int res=0;
 
	for(int i=bas;i<=son;i++) {
 
		res=res*3+(s[i]=='?'?2:(s[i]-'0'));
 
	}
 
	return res;
 
}
 
int main() {
 
	//freopen("input.txt","r",stdin);
 
	po3[0]=po2[0]=1;
 
 	for(int i=1;i<=15;i++) po3[i]=po3[i-1]*3;

 	for(int i=1;i<=20;i++) po2[i]=po2[i-1]*2;
 
	scanf("%d %d",&l,&q);
 
	n=po2[l];
 
	scanf("%s",s);
 
	for(int i=0;i<n;i++) val[i]=s[i]-'0';
 
	for(int i=1;i<=q;i++) {
 
		scanf("%s",s+20-l);
 
		for(int i=0;i<20-l;i++) s[i]='0';
 
		Right[i]=get_value(L,19);
		Left[i]=get_value(0,L-1);
 
	}
 
	pre_cal();
 
	for(int i=0;i<po2[L];i++) {
 
		do_dp(i);
 
		for(int j=1;j<=q;j++) {

			if(inc[Left[j]][i]) {

				ans[j]+=cnt[Right[j]];

			}

		}
 
	}
 
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
 
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:152: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:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:162: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
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	505 ms	13304 KB	Output is correct
2	Correct	491 ms	13540 KB	Output is correct
3	Correct	496 ms	13540 KB	Output is correct
4	Correct	491 ms	13540 KB	Output is correct
5	Correct	589 ms	13540 KB	Output is correct
6	Correct	494 ms	13564 KB	Output is correct
7	Correct	478 ms	13564 KB	Output is correct
8	Correct	529 ms	13564 KB	Output is correct
9	Correct	498 ms	13564 KB	Output is correct
10	Correct	479 ms	13600 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	505 ms	13304 KB	Output is correct
2	Correct	491 ms	13540 KB	Output is correct
3	Correct	496 ms	13540 KB	Output is correct
4	Correct	491 ms	13540 KB	Output is correct
5	Correct	589 ms	13540 KB	Output is correct
6	Correct	494 ms	13564 KB	Output is correct
7	Correct	478 ms	13564 KB	Output is correct
8	Correct	529 ms	13564 KB	Output is correct
9	Correct	498 ms	13564 KB	Output is correct
10	Correct	479 ms	13600 KB	Output is correct
11	Correct	953 ms	27220 KB	Output is correct
12	Correct	1032 ms	27220 KB	Output is correct
13	Correct	933 ms	27220 KB	Output is correct
14	Correct	923 ms	27220 KB	Output is correct
15	Correct	868 ms	27304 KB	Output is correct
16	Correct	916 ms	27304 KB	Output is correct
17	Correct	961 ms	27304 KB	Output is correct
18	Correct	915 ms	28404 KB	Output is correct
19	Correct	889 ms	28404 KB	Output is correct
20	Correct	990 ms	28404 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	505 ms	13304 KB	Output is correct
2	Correct	491 ms	13540 KB	Output is correct
3	Correct	496 ms	13540 KB	Output is correct
4	Correct	491 ms	13540 KB	Output is correct
5	Correct	589 ms	13540 KB	Output is correct
6	Correct	494 ms	13564 KB	Output is correct
7	Correct	478 ms	13564 KB	Output is correct
8	Correct	529 ms	13564 KB	Output is correct
9	Correct	498 ms	13564 KB	Output is correct
10	Correct	479 ms	13600 KB	Output is correct
11	Correct	953 ms	27220 KB	Output is correct
12	Correct	1032 ms	27220 KB	Output is correct
13	Correct	933 ms	27220 KB	Output is correct
14	Correct	923 ms	27220 KB	Output is correct
15	Correct	868 ms	27304 KB	Output is correct
16	Correct	916 ms	27304 KB	Output is correct
17	Correct	961 ms	27304 KB	Output is correct
18	Correct	915 ms	28404 KB	Output is correct
19	Correct	889 ms	28404 KB	Output is correct
20	Correct	990 ms	28404 KB	Output is correct
21	Correct	972 ms	28404 KB	Output is correct
22	Correct	1006 ms	28404 KB	Output is correct
23	Correct	1037 ms	28404 KB	Output is correct
24	Correct	1014 ms	28404 KB	Output is correct
25	Correct	1035 ms	28584 KB	Output is correct
26	Correct	1175 ms	28584 KB	Output is correct
27	Correct	1041 ms	28584 KB	Output is correct
28	Correct	920 ms	29380 KB	Output is correct
29	Correct	963 ms	29380 KB	Output is correct
30	Correct	1002 ms	29380 KB	Output is correct
31	Correct	1046 ms	29380 KB	Output is correct
32	Correct	1046 ms	29380 KB	Output is correct
33	Correct	1093 ms	29380 KB	Output is correct
34	Correct	1121 ms	29380 KB	Output is correct
35	Correct	1183 ms	29380 KB	Output is correct
36	Correct	1026 ms	29380 KB	Output is correct
37	Correct	1242 ms	29380 KB	Output is correct
38	Correct	1194 ms	29380 KB	Output is correct
39	Correct	1253 ms	29380 KB	Output is correct
40	Correct	1114 ms	29380 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	505 ms	13304 KB	Output is correct
2	Correct	491 ms	13540 KB	Output is correct
3	Correct	496 ms	13540 KB	Output is correct
4	Correct	491 ms	13540 KB	Output is correct
5	Correct	589 ms	13540 KB	Output is correct
6	Correct	494 ms	13564 KB	Output is correct
7	Correct	478 ms	13564 KB	Output is correct
8	Correct	529 ms	13564 KB	Output is correct
9	Correct	498 ms	13564 KB	Output is correct
10	Correct	479 ms	13600 KB	Output is correct
11	Incorrect	716 ms	29380 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	505 ms	13304 KB	Output is correct
2	Correct	491 ms	13540 KB	Output is correct
3	Correct	496 ms	13540 KB	Output is correct
4	Correct	491 ms	13540 KB	Output is correct
5	Correct	589 ms	13540 KB	Output is correct
6	Correct	494 ms	13564 KB	Output is correct
7	Correct	478 ms	13564 KB	Output is correct
8	Correct	529 ms	13564 KB	Output is correct
9	Correct	498 ms	13564 KB	Output is correct
10	Correct	479 ms	13600 KB	Output is correct
11	Correct	953 ms	27220 KB	Output is correct
12	Correct	1032 ms	27220 KB	Output is correct
13	Correct	933 ms	27220 KB	Output is correct
14	Correct	923 ms	27220 KB	Output is correct
15	Correct	868 ms	27304 KB	Output is correct
16	Correct	916 ms	27304 KB	Output is correct
17	Correct	961 ms	27304 KB	Output is correct
18	Correct	915 ms	28404 KB	Output is correct
19	Correct	889 ms	28404 KB	Output is correct
20	Correct	990 ms	28404 KB	Output is correct
21	Correct	972 ms	28404 KB	Output is correct
22	Correct	1006 ms	28404 KB	Output is correct
23	Correct	1037 ms	28404 KB	Output is correct
24	Correct	1014 ms	28404 KB	Output is correct
25	Correct	1035 ms	28584 KB	Output is correct
26	Correct	1175 ms	28584 KB	Output is correct
27	Correct	1041 ms	28584 KB	Output is correct
28	Correct	920 ms	29380 KB	Output is correct
29	Correct	963 ms	29380 KB	Output is correct
30	Correct	1002 ms	29380 KB	Output is correct
31	Correct	1046 ms	29380 KB	Output is correct
32	Correct	1046 ms	29380 KB	Output is correct
33	Correct	1093 ms	29380 KB	Output is correct
34	Correct	1121 ms	29380 KB	Output is correct
35	Correct	1183 ms	29380 KB	Output is correct
36	Correct	1026 ms	29380 KB	Output is correct
37	Correct	1242 ms	29380 KB	Output is correct
38	Correct	1194 ms	29380 KB	Output is correct
39	Correct	1253 ms	29380 KB	Output is correct
40	Correct	1114 ms	29380 KB	Output is correct
41	Incorrect	716 ms	29380 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #66938

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.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
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0