답안 #329329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
329329	2020-11-20T15:22:15 Z	HoneyBadger	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	922 ms	65540 KB

snake_escaping

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <ctime>
#include <chrono>
#include <unordered_map>


#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")



#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else
    #define dbg(x)
#endif

#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a, b) for (int i = a; i < b; i++)
#define fj(a, b) for (int j = a; j < b; j++)
#define fk(a, b) for (int k = a; k < b; k++)
#define fi1(a, b) for (int i = a - 1; i >= b; i--)
#define fj1(a, b) for (int j = a - 1; j >= b; j--)
#define fk1(a, b) for (int k = a - 1; k >= b; k--)
#define fx(x, a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; }

ostream& operator << (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << ' ';
    return out;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const double EPS = 1e-9;
const int BUBEN = 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int n, q;
ll pw3[21];
int a[1 << 20];

unordered_map<ll, int> ht;
void init() {
    pw3[0] = 1;
    fi(1, 21) pw3[i] = pw3[i - 1] * 3;
    ht.reserve(1 << 21);
    ht.max_load_factor(0.25);
}

//pos3.size() <= BUBEN slow

int gen(int mask, vi &pos3) {
	if (pos3.empty())
		return a[mask];
	int i = pos3.back();
	pos3.ppb;
	int res = gen(mask + (1 << i), pos3) + gen(mask, pos3); 
	pos3.pb(i);
	return res;
}

int get(ll mask3, int mask2, vi &pos3) {
	if (pos3.size() <= BUBEN) {
		return gen(mask2, pos3);
	}
	auto it = ht.find(mask3);
	if (it == ht.end()) {
		int i = pos3.back();
		pos3.ppb;
		int res = get(mask3 - pw3[i], mask2 ^ (1 << i), pos3) + get(mask3 - 2 * pw3[i], mask2, pos3);
		pos3.pb(i);
		ht[mask3] = res;
		return res;
	} else {
		return it->second;
	}
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();

    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i) {
    	char c;
    	cin >> c;
    	a[i] = c - '0';
    }
    while (q--) {
    	vi pos3;
    	ll mask3 = 0;
    	int mask2 = 0;
    	fi(0, n) {
    		char c;
    		cin >> c;
    		if (c == '1') {
    			mask2 += 1 << (n - i - 1);
    			mask3 += 1 * pw3[n - i - 1];
    		} else if (c == '?') {
    			mask3 += 2 * pw3[n - i - 1];
    			pos3.pb(n - i - 1);
    		}	
    	}
    	cout << get(mask3, mask2, pos3) << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	17132 KB	Output is correct
2	Correct	13 ms	17132 KB	Output is correct
3	Correct	12 ms	17132 KB	Output is correct
4	Correct	12 ms	17132 KB	Output is correct
5	Correct	13 ms	17132 KB	Output is correct
6	Correct	13 ms	17132 KB	Output is correct
7	Correct	13 ms	17132 KB	Output is correct
8	Correct	12 ms	17132 KB	Output is correct
9	Correct	13 ms	17132 KB	Output is correct
10	Correct	13 ms	17132 KB	Output is correct
11	Correct	677 ms	23276 KB	Output is correct
12	Correct	541 ms	22352 KB	Output is correct
13	Correct	457 ms	21484 KB	Output is correct
14	Correct	487 ms	21628 KB	Output is correct
15	Correct	505 ms	22892 KB	Output is correct
16	Correct	542 ms	22252 KB	Output is correct
17	Correct	531 ms	22124 KB	Output is correct
18	Correct	441 ms	23788 KB	Output is correct
19	Correct	346 ms	20844 KB	Output is correct
20	Correct	563 ms	22636 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	17132 KB	Output is correct
2	Correct	13 ms	17132 KB	Output is correct
3	Correct	12 ms	17132 KB	Output is correct
4	Correct	12 ms	17132 KB	Output is correct
5	Correct	13 ms	17132 KB	Output is correct
6	Correct	13 ms	17132 KB	Output is correct
7	Correct	13 ms	17132 KB	Output is correct
8	Correct	12 ms	17132 KB	Output is correct
9	Correct	13 ms	17132 KB	Output is correct
10	Correct	13 ms	17132 KB	Output is correct
11	Correct	677 ms	23276 KB	Output is correct
12	Correct	541 ms	22352 KB	Output is correct
13	Correct	457 ms	21484 KB	Output is correct
14	Correct	487 ms	21628 KB	Output is correct
15	Correct	505 ms	22892 KB	Output is correct
16	Correct	542 ms	22252 KB	Output is correct
17	Correct	531 ms	22124 KB	Output is correct
18	Correct	441 ms	23788 KB	Output is correct
19	Correct	346 ms	20844 KB	Output is correct
20	Correct	563 ms	22636 KB	Output is correct
21	Correct	592 ms	23276 KB	Output is correct
22	Correct	642 ms	23660 KB	Output is correct
23	Correct	621 ms	22764 KB	Output is correct
24	Correct	601 ms	21996 KB	Output is correct
25	Correct	778 ms	28780 KB	Output is correct
26	Correct	754 ms	25964 KB	Output is correct
27	Correct	775 ms	29652 KB	Output is correct
28	Correct	513 ms	24104 KB	Output is correct
29	Correct	416 ms	20204 KB	Output is correct
30	Correct	671 ms	22892 KB	Output is correct
31	Correct	922 ms	28688 KB	Output is correct
32	Correct	789 ms	22508 KB	Output is correct
33	Correct	532 ms	21100 KB	Output is correct
34	Correct	600 ms	21100 KB	Output is correct
35	Correct	783 ms	29292 KB	Output is correct
36	Correct	313 ms	20076 KB	Output is correct
37	Correct	579 ms	22508 KB	Output is correct
38	Correct	427 ms	20356 KB	Output is correct
39	Correct	658 ms	22124 KB	Output is correct
40	Correct	635 ms	21184 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	17132 KB	Output is correct
2	Correct	13 ms	17132 KB	Output is correct
3	Correct	12 ms	17132 KB	Output is correct
4	Correct	12 ms	17132 KB	Output is correct
5	Correct	13 ms	17132 KB	Output is correct
6	Correct	13 ms	17132 KB	Output is correct
7	Correct	13 ms	17132 KB	Output is correct
8	Correct	12 ms	17132 KB	Output is correct
9	Correct	13 ms	17132 KB	Output is correct
10	Correct	13 ms	17132 KB	Output is correct
11	Runtime error	322 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	17132 KB	Output is correct
2	Correct	13 ms	17132 KB	Output is correct
3	Correct	12 ms	17132 KB	Output is correct
4	Correct	12 ms	17132 KB	Output is correct
5	Correct	13 ms	17132 KB	Output is correct
6	Correct	13 ms	17132 KB	Output is correct
7	Correct	13 ms	17132 KB	Output is correct
8	Correct	12 ms	17132 KB	Output is correct
9	Correct	13 ms	17132 KB	Output is correct
10	Correct	13 ms	17132 KB	Output is correct
11	Correct	677 ms	23276 KB	Output is correct
12	Correct	541 ms	22352 KB	Output is correct
13	Correct	457 ms	21484 KB	Output is correct
14	Correct	487 ms	21628 KB	Output is correct
15	Correct	505 ms	22892 KB	Output is correct
16	Correct	542 ms	22252 KB	Output is correct
17	Correct	531 ms	22124 KB	Output is correct
18	Correct	441 ms	23788 KB	Output is correct
19	Correct	346 ms	20844 KB	Output is correct
20	Correct	563 ms	22636 KB	Output is correct
21	Correct	592 ms	23276 KB	Output is correct
22	Correct	642 ms	23660 KB	Output is correct
23	Correct	621 ms	22764 KB	Output is correct
24	Correct	601 ms	21996 KB	Output is correct
25	Correct	778 ms	28780 KB	Output is correct
26	Correct	754 ms	25964 KB	Output is correct
27	Correct	775 ms	29652 KB	Output is correct
28	Correct	513 ms	24104 KB	Output is correct
29	Correct	416 ms	20204 KB	Output is correct
30	Correct	671 ms	22892 KB	Output is correct
31	Correct	922 ms	28688 KB	Output is correct
32	Correct	789 ms	22508 KB	Output is correct
33	Correct	532 ms	21100 KB	Output is correct
34	Correct	600 ms	21100 KB	Output is correct
35	Correct	783 ms	29292 KB	Output is correct
36	Correct	313 ms	20076 KB	Output is correct
37	Correct	579 ms	22508 KB	Output is correct
38	Correct	427 ms	20356 KB	Output is correct
39	Correct	658 ms	22124 KB	Output is correct
40	Correct	635 ms	21184 KB	Output is correct
41	Runtime error	322 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

답안 #329329

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