답안 #828099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828099	2023-08-17T04:31:23 Z	NhanBeoo	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	2000 ms	65536 KB

snake_escaping

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

#include <bits/stdc++.h>
using namespace std;

// #define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;

struct Trie{
	struct Node{
		int cnt, exist, sum;
		Node* child[2];
		Node(){
			cnt = exist = sum = 0;
			child[0] = child[1] = NULL;
		}
	};
	Node* root;
	Trie(){
		root = new Node();
	}
	int LG;
	void init(int n){
		LG = n-1;
	}
	void add(int n, int val){
		Node* p = root;
		for(int i=LG; i>=0; i--){
			bool c = n & (1<<i);
			if(p->child[c] == NULL) p->child[c] = new Node();
			p = p->child[c];
			p->cnt++;
		}
		p->exist++;
		p->sum += val;
	}
	int dequy(Node* p, string& s, int i){
		if(i == LG + 1) return p->sum;
		if(s[i] == '0') return dequy(p->child[0], s, i+1);
		else if(s[i] == '1') return dequy(p->child[1], s, i+1);
		else return dequy(p->child[0], s, i+1) + dequy(p->child[1], s, i+1);
	}
	int find(string s){
		return dequy(root, s, 0);
	}
} trie;

map<string, int> m;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, q; cin >> n >> q;
	string s; cin >> s;
	trie.init(n);
	for(int i=0; i<(1<<n); i++) trie.add(i, s[i] - '0');
	while(q--){
		string tmp; cin >> tmp;
		if(m[tmp] != 0) cout << m[tmp] << endl;
		else{
			int ans = trie.find(tmp);
			m[tmp] = ans;
			cout << ans << endl;
		}
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	246 ms	4352 KB	Output is correct
12	Correct	334 ms	4116 KB	Output is correct
13	Correct	438 ms	3888 KB	Output is correct
14	Correct	404 ms	3672 KB	Output is correct
15	Correct	397 ms	4636 KB	Output is correct
16	Correct	487 ms	4740 KB	Output is correct
17	Correct	579 ms	8100 KB	Output is correct
18	Correct	142 ms	5328 KB	Output is correct
19	Correct	245 ms	2380 KB	Output is correct
20	Correct	338 ms	4080 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	246 ms	4352 KB	Output is correct
12	Correct	334 ms	4116 KB	Output is correct
13	Correct	438 ms	3888 KB	Output is correct
14	Correct	404 ms	3672 KB	Output is correct
15	Correct	397 ms	4636 KB	Output is correct
16	Correct	487 ms	4740 KB	Output is correct
17	Correct	579 ms	8100 KB	Output is correct
18	Correct	142 ms	5328 KB	Output is correct
19	Correct	245 ms	2380 KB	Output is correct
20	Correct	338 ms	4080 KB	Output is correct
21	Correct	406 ms	5244 KB	Output is correct
22	Correct	468 ms	5856 KB	Output is correct
23	Correct	1030 ms	21188 KB	Output is correct
24	Correct	686 ms	11284 KB	Output is correct
25	Correct	670 ms	9332 KB	Output is correct
26	Correct	1405 ms	31408 KB	Output is correct
27	Execution timed out	2021 ms	65536 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Runtime error	73 ms	65536 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	246 ms	4352 KB	Output is correct
12	Correct	334 ms	4116 KB	Output is correct
13	Correct	438 ms	3888 KB	Output is correct
14	Correct	404 ms	3672 KB	Output is correct
15	Correct	397 ms	4636 KB	Output is correct
16	Correct	487 ms	4740 KB	Output is correct
17	Correct	579 ms	8100 KB	Output is correct
18	Correct	142 ms	5328 KB	Output is correct
19	Correct	245 ms	2380 KB	Output is correct
20	Correct	338 ms	4080 KB	Output is correct
21	Correct	406 ms	5244 KB	Output is correct
22	Correct	468 ms	5856 KB	Output is correct
23	Correct	1030 ms	21188 KB	Output is correct
24	Correct	686 ms	11284 KB	Output is correct
25	Correct	670 ms	9332 KB	Output is correct
26	Correct	1405 ms	31408 KB	Output is correct
27	Execution timed out	2021 ms	65536 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

답안 #828099

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

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

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0