Submission #66923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66923	2018-08-12T19:19:32 Z	hamzqq9	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1249 ms	65788 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],pos[1594325];
char val[pw(20)+5],s[pw(20)+5];
bool oops[1594325],inc[2188][129];
int Left[pw(20)+5],Right[pw(20)+5];
 
int get_2_rep(int val) {
 
	int res=0;
	int curpw=1;
 
	while(val) {
 
		res+=curpw*(val%3);
 
		val/=3;
 
		curpw*=2;
 
	}
 
	return res;
 
}
 
int get_2(int val) {
 
	int cur=0;
 
	while(val) {
 
		if(val%3==2) return cur;
 
		cur++;
 
		val/=3;
 
	}
 
	return -1;
 
}
 
void do_dp(int value) {
 
	for(int i=0;i<1594323;i++) {
 
		if(oops[i]) cnt[i]=val[value*pw(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+=pw(bit);

	rval+=po3[bit];

	back_track(bit+1);

	rval+=po3[bit];

	back_track(bit+1);

	lval-=pw(bit);

	back_track(bit+1);

	rval-=po3[bit]*2;

	back_track(bit+1);

}

void pre_cal() {
 
	for(int i=0;i<1594323;i++) {
 
		pos[i]=get_2(i);
 
		if(pos[i]==-1) {
		
			oops[i]=true;
 
			pos[i]=get_2_rep(i);
		
		}
 
	}

	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]=1;
 
 	for(int i=1;i<=15;i++) po3[i]=po3[i-1]*3;
 
	scanf("%d %d",&l,&q);
 
	n=pw(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(7,19);
		Left[i]=get_value(0,6);
 
	}
 
	pre_cal();
 
	for(int i=0;i<pw(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:158: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:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:168: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

#	Verdict	Execution time	Memory	Grader output
1	Correct	564 ms	13432 KB	Output is correct
2	Correct	456 ms	13492 KB	Output is correct
3	Correct	471 ms	13492 KB	Output is correct
4	Correct	540 ms	13532 KB	Output is correct
5	Correct	488 ms	13644 KB	Output is correct
6	Correct	463 ms	13644 KB	Output is correct
7	Correct	470 ms	13644 KB	Output is correct
8	Correct	508 ms	13644 KB	Output is correct
9	Correct	531 ms	13644 KB	Output is correct
10	Correct	519 ms	13644 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	564 ms	13432 KB	Output is correct
2	Correct	456 ms	13492 KB	Output is correct
3	Correct	471 ms	13492 KB	Output is correct
4	Correct	540 ms	13532 KB	Output is correct
5	Correct	488 ms	13644 KB	Output is correct
6	Correct	463 ms	13644 KB	Output is correct
7	Correct	470 ms	13644 KB	Output is correct
8	Correct	508 ms	13644 KB	Output is correct
9	Correct	531 ms	13644 KB	Output is correct
10	Correct	519 ms	13644 KB	Output is correct
11	Correct	964 ms	29108 KB	Output is correct
12	Correct	996 ms	29108 KB	Output is correct
13	Correct	983 ms	29108 KB	Output is correct
14	Correct	1018 ms	29108 KB	Output is correct
15	Correct	965 ms	29188 KB	Output is correct
16	Correct	945 ms	29188 KB	Output is correct
17	Correct	924 ms	29188 KB	Output is correct
18	Correct	869 ms	30304 KB	Output is correct
19	Correct	876 ms	30304 KB	Output is correct
20	Correct	944 ms	30304 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	564 ms	13432 KB	Output is correct
2	Correct	456 ms	13492 KB	Output is correct
3	Correct	471 ms	13492 KB	Output is correct
4	Correct	540 ms	13532 KB	Output is correct
5	Correct	488 ms	13644 KB	Output is correct
6	Correct	463 ms	13644 KB	Output is correct
7	Correct	470 ms	13644 KB	Output is correct
8	Correct	508 ms	13644 KB	Output is correct
9	Correct	531 ms	13644 KB	Output is correct
10	Correct	519 ms	13644 KB	Output is correct
11	Correct	964 ms	29108 KB	Output is correct
12	Correct	996 ms	29108 KB	Output is correct
13	Correct	983 ms	29108 KB	Output is correct
14	Correct	1018 ms	29108 KB	Output is correct
15	Correct	965 ms	29188 KB	Output is correct
16	Correct	945 ms	29188 KB	Output is correct
17	Correct	924 ms	29188 KB	Output is correct
18	Correct	869 ms	30304 KB	Output is correct
19	Correct	876 ms	30304 KB	Output is correct
20	Correct	944 ms	30304 KB	Output is correct
21	Correct	945 ms	30304 KB	Output is correct
22	Correct	991 ms	30304 KB	Output is correct
23	Correct	1249 ms	30304 KB	Output is correct
24	Correct	1039 ms	30304 KB	Output is correct
25	Correct	952 ms	30380 KB	Output is correct
26	Correct	1036 ms	30380 KB	Output is correct
27	Correct	1215 ms	30380 KB	Output is correct
28	Correct	947 ms	31276 KB	Output is correct
29	Correct	930 ms	31276 KB	Output is correct
30	Correct	1033 ms	31276 KB	Output is correct
31	Correct	976 ms	31276 KB	Output is correct
32	Correct	955 ms	31276 KB	Output is correct
33	Correct	946 ms	31276 KB	Output is correct
34	Correct	991 ms	31276 KB	Output is correct
35	Correct	1022 ms	31276 KB	Output is correct
36	Correct	1069 ms	31276 KB	Output is correct
37	Correct	1006 ms	31276 KB	Output is correct
38	Correct	926 ms	31276 KB	Output is correct
39	Correct	1010 ms	31276 KB	Output is correct
40	Correct	931 ms	31276 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	564 ms	13432 KB	Output is correct
2	Correct	456 ms	13492 KB	Output is correct
3	Correct	471 ms	13492 KB	Output is correct
4	Correct	540 ms	13532 KB	Output is correct
5	Correct	488 ms	13644 KB	Output is correct
6	Correct	463 ms	13644 KB	Output is correct
7	Correct	470 ms	13644 KB	Output is correct
8	Correct	508 ms	13644 KB	Output is correct
9	Correct	531 ms	13644 KB	Output is correct
10	Correct	519 ms	13644 KB	Output is correct
11	Correct	585 ms	31276 KB	Output is correct
12	Correct	606 ms	31276 KB	Output is correct
13	Correct	603 ms	31276 KB	Output is correct
14	Correct	577 ms	31276 KB	Output is correct
15	Correct	591 ms	31276 KB	Output is correct
16	Correct	585 ms	31276 KB	Output is correct
17	Correct	598 ms	31276 KB	Output is correct
18	Correct	599 ms	31276 KB	Output is correct
19	Correct	565 ms	31276 KB	Output is correct
20	Correct	579 ms	31276 KB	Output is correct
21	Correct	609 ms	31276 KB	Output is correct
22	Correct	593 ms	31276 KB	Output is correct
23	Correct	582 ms	33012 KB	Output is correct
24	Correct	592 ms	35056 KB	Output is correct
25	Correct	622 ms	36996 KB	Output is correct
26	Correct	582 ms	39024 KB	Output is correct
27	Correct	677 ms	41236 KB	Output is correct
28	Correct	564 ms	43032 KB	Output is correct
29	Correct	610 ms	45220 KB	Output is correct
30	Correct	566 ms	47392 KB	Output is correct
31	Correct	532 ms	49456 KB	Output is correct
32	Correct	637 ms	51592 KB	Output is correct
33	Correct	567 ms	53536 KB	Output is correct
34	Correct	531 ms	55380 KB	Output is correct
35	Correct	641 ms	57684 KB	Output is correct
36	Correct	625 ms	59720 KB	Output is correct
37	Correct	817 ms	61660 KB	Output is correct
38	Correct	620 ms	63840 KB	Output is correct
39	Runtime error	780 ms	65788 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
40	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	564 ms	13432 KB	Output is correct
2	Correct	456 ms	13492 KB	Output is correct
3	Correct	471 ms	13492 KB	Output is correct
4	Correct	540 ms	13532 KB	Output is correct
5	Correct	488 ms	13644 KB	Output is correct
6	Correct	463 ms	13644 KB	Output is correct
7	Correct	470 ms	13644 KB	Output is correct
8	Correct	508 ms	13644 KB	Output is correct
9	Correct	531 ms	13644 KB	Output is correct
10	Correct	519 ms	13644 KB	Output is correct
11	Correct	964 ms	29108 KB	Output is correct
12	Correct	996 ms	29108 KB	Output is correct
13	Correct	983 ms	29108 KB	Output is correct
14	Correct	1018 ms	29108 KB	Output is correct
15	Correct	965 ms	29188 KB	Output is correct
16	Correct	945 ms	29188 KB	Output is correct
17	Correct	924 ms	29188 KB	Output is correct
18	Correct	869 ms	30304 KB	Output is correct
19	Correct	876 ms	30304 KB	Output is correct
20	Correct	944 ms	30304 KB	Output is correct
21	Correct	945 ms	30304 KB	Output is correct
22	Correct	991 ms	30304 KB	Output is correct
23	Correct	1249 ms	30304 KB	Output is correct
24	Correct	1039 ms	30304 KB	Output is correct
25	Correct	952 ms	30380 KB	Output is correct
26	Correct	1036 ms	30380 KB	Output is correct
27	Correct	1215 ms	30380 KB	Output is correct
28	Correct	947 ms	31276 KB	Output is correct
29	Correct	930 ms	31276 KB	Output is correct
30	Correct	1033 ms	31276 KB	Output is correct
31	Correct	976 ms	31276 KB	Output is correct
32	Correct	955 ms	31276 KB	Output is correct
33	Correct	946 ms	31276 KB	Output is correct
34	Correct	991 ms	31276 KB	Output is correct
35	Correct	1022 ms	31276 KB	Output is correct
36	Correct	1069 ms	31276 KB	Output is correct
37	Correct	1006 ms	31276 KB	Output is correct
38	Correct	926 ms	31276 KB	Output is correct
39	Correct	1010 ms	31276 KB	Output is correct
40	Correct	931 ms	31276 KB	Output is correct
41	Correct	585 ms	31276 KB	Output is correct
42	Correct	606 ms	31276 KB	Output is correct
43	Correct	603 ms	31276 KB	Output is correct
44	Correct	577 ms	31276 KB	Output is correct
45	Correct	591 ms	31276 KB	Output is correct
46	Correct	585 ms	31276 KB	Output is correct
47	Correct	598 ms	31276 KB	Output is correct
48	Correct	599 ms	31276 KB	Output is correct
49	Correct	565 ms	31276 KB	Output is correct
50	Correct	579 ms	31276 KB	Output is correct
51	Correct	609 ms	31276 KB	Output is correct
52	Correct	593 ms	31276 KB	Output is correct
53	Correct	582 ms	33012 KB	Output is correct
54	Correct	592 ms	35056 KB	Output is correct
55	Correct	622 ms	36996 KB	Output is correct
56	Correct	582 ms	39024 KB	Output is correct
57	Correct	677 ms	41236 KB	Output is correct
58	Correct	564 ms	43032 KB	Output is correct
59	Correct	610 ms	45220 KB	Output is correct
60	Correct	566 ms	47392 KB	Output is correct
61	Correct	532 ms	49456 KB	Output is correct
62	Correct	637 ms	51592 KB	Output is correct
63	Correct	567 ms	53536 KB	Output is correct
64	Correct	531 ms	55380 KB	Output is correct
65	Correct	641 ms	57684 KB	Output is correct
66	Correct	625 ms	59720 KB	Output is correct
67	Correct	817 ms	61660 KB	Output is correct
68	Correct	620 ms	63840 KB	Output is correct
69	Runtime error	780 ms	65788 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
70	Halted	0 ms	0 KB	-

Submission #66923

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