Submission #333117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333117	2020-12-04T16:40:43 Z	soroush	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	419 ms	13036 KB

snake_escaping

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll maxn  = 2e6+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int l , q;
int a[maxn];
string s;
 
int ans[maxn];
 
int p[30];

void sub1(){
	for(int i = 0 ; i < p[l] ; i ++){
		int res = 0;
		int x = i;
		for(int j = l ; j >= 0 ; j --){
			if(x >= 2*p[j]){
				x = i;
				x-=2*p[j];
				ans[i] = ans[x] + ans[x + p[j]];
				break;
			}
			if(x >= p[j])
				res += (1 << j);
			x%=p[j];
			if(j == 0)ans[i] = a[res];
		}
	}
	while(q -- ){
		string t;
		cin >> t;
		reverse(t.begin() , t.end());
		int x = 0;
		for(int i = 0 ; i < l ; i ++)
			if(t[i] == '?')x+=p[i]*2;
			else if(t[i] == '1')x+=p[i];
		cout << ans[x] << endl;
	}
	exit(0);
}

vector < string > t;
int res[maxn];

int32_t main(){
    migmig;
    cin >> l >> q;
    cin >> s;
    for(int i = 0 ; i < (1 << l) ; i ++)
		a[i] = s[i] - '0';
	p[0] = 1;
	for(int i = 1 ; i < 16; i ++)
		p[i] = p[i - 1] * 3;
	if(l <= 15)
		sub1();
	
    return(0);
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	232 ms	5028 KB	Output is correct
12	Correct	248 ms	4716 KB	Output is correct
13	Correct	247 ms	3820 KB	Output is correct
14	Correct	254 ms	3820 KB	Output is correct
15	Correct	252 ms	4844 KB	Output is correct
16	Correct	260 ms	3948 KB	Output is correct
17	Correct	271 ms	3948 KB	Output is correct
18	Correct	193 ms	5868 KB	Output is correct
19	Correct	242 ms	2796 KB	Output is correct
20	Correct	251 ms	4588 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	232 ms	5028 KB	Output is correct
12	Correct	248 ms	4716 KB	Output is correct
13	Correct	247 ms	3820 KB	Output is correct
14	Correct	254 ms	3820 KB	Output is correct
15	Correct	252 ms	4844 KB	Output is correct
16	Correct	260 ms	3948 KB	Output is correct
17	Correct	271 ms	3948 KB	Output is correct
18	Correct	193 ms	5868 KB	Output is correct
19	Correct	242 ms	2796 KB	Output is correct
20	Correct	251 ms	4588 KB	Output is correct
21	Correct	288 ms	11008 KB	Output is correct
22	Correct	311 ms	11116 KB	Output is correct
23	Correct	360 ms	10092 KB	Output is correct
24	Correct	357 ms	9964 KB	Output is correct
25	Correct	337 ms	12012 KB	Output is correct
26	Correct	395 ms	10732 KB	Output is correct
27	Correct	410 ms	10512 KB	Output is correct
28	Correct	231 ms	13036 KB	Output is correct
29	Correct	285 ms	8912 KB	Output is correct
30	Correct	304 ms	11116 KB	Output is correct
31	Correct	376 ms	10988 KB	Output is correct
32	Correct	367 ms	10988 KB	Output is correct
33	Correct	298 ms	9964 KB	Output is correct
34	Correct	378 ms	9964 KB	Output is correct
35	Correct	419 ms	10604 KB	Output is correct
36	Correct	215 ms	8940 KB	Output is correct
37	Correct	282 ms	10988 KB	Output is correct
38	Correct	296 ms	8940 KB	Output is correct
39	Correct	372 ms	10092 KB	Output is correct
40	Correct	356 ms	10092 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Incorrect	6 ms	5648 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct
11	Correct	232 ms	5028 KB	Output is correct
12	Correct	248 ms	4716 KB	Output is correct
13	Correct	247 ms	3820 KB	Output is correct
14	Correct	254 ms	3820 KB	Output is correct
15	Correct	252 ms	4844 KB	Output is correct
16	Correct	260 ms	3948 KB	Output is correct
17	Correct	271 ms	3948 KB	Output is correct
18	Correct	193 ms	5868 KB	Output is correct
19	Correct	242 ms	2796 KB	Output is correct
20	Correct	251 ms	4588 KB	Output is correct
21	Correct	288 ms	11008 KB	Output is correct
22	Correct	311 ms	11116 KB	Output is correct
23	Correct	360 ms	10092 KB	Output is correct
24	Correct	357 ms	9964 KB	Output is correct
25	Correct	337 ms	12012 KB	Output is correct
26	Correct	395 ms	10732 KB	Output is correct
27	Correct	410 ms	10512 KB	Output is correct
28	Correct	231 ms	13036 KB	Output is correct
29	Correct	285 ms	8912 KB	Output is correct
30	Correct	304 ms	11116 KB	Output is correct
31	Correct	376 ms	10988 KB	Output is correct
32	Correct	367 ms	10988 KB	Output is correct
33	Correct	298 ms	9964 KB	Output is correct
34	Correct	378 ms	9964 KB	Output is correct
35	Correct	419 ms	10604 KB	Output is correct
36	Correct	215 ms	8940 KB	Output is correct
37	Correct	282 ms	10988 KB	Output is correct
38	Correct	296 ms	8940 KB	Output is correct
39	Correct	372 ms	10092 KB	Output is correct
40	Correct	356 ms	10092 KB	Output is correct
41	Incorrect	6 ms	5648 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #333117

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