답안 #333115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333115	2020-12-04T16:38:38 Z	soroush	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	426 ms	13164 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);
}

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	244 ms	4844 KB	Output is correct
12	Correct	284 ms	4460 KB	Output is correct
13	Correct	259 ms	3692 KB	Output is correct
14	Correct	261 ms	3692 KB	Output is correct
15	Correct	268 ms	4844 KB	Output is correct
16	Correct	271 ms	4076 KB	Output is correct
17	Correct	282 ms	3820 KB	Output is correct
18	Correct	206 ms	5836 KB	Output is correct
19	Correct	237 ms	3040 KB	Output is correct
20	Correct	259 ms	4376 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	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	244 ms	4844 KB	Output is correct
12	Correct	284 ms	4460 KB	Output is correct
13	Correct	259 ms	3692 KB	Output is correct
14	Correct	261 ms	3692 KB	Output is correct
15	Correct	268 ms	4844 KB	Output is correct
16	Correct	271 ms	4076 KB	Output is correct
17	Correct	282 ms	3820 KB	Output is correct
18	Correct	206 ms	5836 KB	Output is correct
19	Correct	237 ms	3040 KB	Output is correct
20	Correct	259 ms	4376 KB	Output is correct
21	Correct	299 ms	11116 KB	Output is correct
22	Correct	319 ms	11116 KB	Output is correct
23	Correct	392 ms	10220 KB	Output is correct
24	Correct	392 ms	9964 KB	Output is correct
25	Correct	350 ms	11884 KB	Output is correct
26	Correct	394 ms	10476 KB	Output is correct
27	Correct	424 ms	10636 KB	Output is correct
28	Correct	245 ms	13164 KB	Output is correct
29	Correct	288 ms	8940 KB	Output is correct
30	Correct	317 ms	11244 KB	Output is correct
31	Correct	425 ms	10988 KB	Output is correct
32	Correct	395 ms	10988 KB	Output is correct
33	Correct	314 ms	9804 KB	Output is correct
34	Correct	414 ms	10092 KB	Output is correct
35	Correct	426 ms	10348 KB	Output is correct
36	Correct	231 ms	8920 KB	Output is correct
37	Correct	299 ms	10976 KB	Output is correct
38	Correct	310 ms	8940 KB	Output is correct
39	Correct	376 ms	10540 KB	Output is correct
40	Correct	387 ms	9964 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	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	9 ms	6800 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	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	244 ms	4844 KB	Output is correct
12	Correct	284 ms	4460 KB	Output is correct
13	Correct	259 ms	3692 KB	Output is correct
14	Correct	261 ms	3692 KB	Output is correct
15	Correct	268 ms	4844 KB	Output is correct
16	Correct	271 ms	4076 KB	Output is correct
17	Correct	282 ms	3820 KB	Output is correct
18	Correct	206 ms	5836 KB	Output is correct
19	Correct	237 ms	3040 KB	Output is correct
20	Correct	259 ms	4376 KB	Output is correct
21	Correct	299 ms	11116 KB	Output is correct
22	Correct	319 ms	11116 KB	Output is correct
23	Correct	392 ms	10220 KB	Output is correct
24	Correct	392 ms	9964 KB	Output is correct
25	Correct	350 ms	11884 KB	Output is correct
26	Correct	394 ms	10476 KB	Output is correct
27	Correct	424 ms	10636 KB	Output is correct
28	Correct	245 ms	13164 KB	Output is correct
29	Correct	288 ms	8940 KB	Output is correct
30	Correct	317 ms	11244 KB	Output is correct
31	Correct	425 ms	10988 KB	Output is correct
32	Correct	395 ms	10988 KB	Output is correct
33	Correct	314 ms	9804 KB	Output is correct
34	Correct	414 ms	10092 KB	Output is correct
35	Correct	426 ms	10348 KB	Output is correct
36	Correct	231 ms	8920 KB	Output is correct
37	Correct	299 ms	10976 KB	Output is correct
38	Correct	310 ms	8940 KB	Output is correct
39	Correct	376 ms	10540 KB	Output is correct
40	Correct	387 ms	9964 KB	Output is correct
41	Incorrect	9 ms	6800 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #333115

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