답안 #329328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
329328	2020-11-20T15:21:03 Z	HoneyBadger	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	946 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 = 4;

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 << 22);
    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	23 ms	34412 KB	Output is correct
2	Correct	23 ms	34540 KB	Output is correct
3	Correct	22 ms	34412 KB	Output is correct
4	Correct	23 ms	34412 KB	Output is correct
5	Correct	23 ms	34540 KB	Output is correct
6	Correct	22 ms	34412 KB	Output is correct
7	Correct	22 ms	34412 KB	Output is correct
8	Correct	22 ms	34412 KB	Output is correct
9	Correct	22 ms	34412 KB	Output is correct
10	Correct	23 ms	34540 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	34412 KB	Output is correct
2	Correct	23 ms	34540 KB	Output is correct
3	Correct	22 ms	34412 KB	Output is correct
4	Correct	23 ms	34412 KB	Output is correct
5	Correct	23 ms	34540 KB	Output is correct
6	Correct	22 ms	34412 KB	Output is correct
7	Correct	22 ms	34412 KB	Output is correct
8	Correct	22 ms	34412 KB	Output is correct
9	Correct	22 ms	34412 KB	Output is correct
10	Correct	23 ms	34540 KB	Output is correct
11	Correct	504 ms	39148 KB	Output is correct
12	Correct	504 ms	38252 KB	Output is correct
13	Correct	463 ms	37612 KB	Output is correct
14	Correct	497 ms	37612 KB	Output is correct
15	Correct	514 ms	39020 KB	Output is correct
16	Correct	538 ms	38124 KB	Output is correct
17	Correct	539 ms	38380 KB	Output is correct
18	Correct	454 ms	40044 KB	Output is correct
19	Correct	350 ms	36844 KB	Output is correct
20	Correct	514 ms	39044 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	34412 KB	Output is correct
2	Correct	23 ms	34540 KB	Output is correct
3	Correct	22 ms	34412 KB	Output is correct
4	Correct	23 ms	34412 KB	Output is correct
5	Correct	23 ms	34540 KB	Output is correct
6	Correct	22 ms	34412 KB	Output is correct
7	Correct	22 ms	34412 KB	Output is correct
8	Correct	22 ms	34412 KB	Output is correct
9	Correct	22 ms	34412 KB	Output is correct
10	Correct	23 ms	34540 KB	Output is correct
11	Correct	504 ms	39148 KB	Output is correct
12	Correct	504 ms	38252 KB	Output is correct
13	Correct	463 ms	37612 KB	Output is correct
14	Correct	497 ms	37612 KB	Output is correct
15	Correct	514 ms	39020 KB	Output is correct
16	Correct	538 ms	38124 KB	Output is correct
17	Correct	539 ms	38380 KB	Output is correct
18	Correct	454 ms	40044 KB	Output is correct
19	Correct	350 ms	36844 KB	Output is correct
20	Correct	514 ms	39044 KB	Output is correct
21	Correct	608 ms	39532 KB	Output is correct
22	Correct	624 ms	39916 KB	Output is correct
23	Correct	627 ms	40300 KB	Output is correct
24	Correct	611 ms	38252 KB	Output is correct
25	Correct	761 ms	46956 KB	Output is correct
26	Correct	766 ms	46316 KB	Output is correct
27	Correct	798 ms	54380 KB	Output is correct
28	Correct	526 ms	41836 KB	Output is correct
29	Correct	432 ms	37868 KB	Output is correct
30	Correct	637 ms	40640 KB	Output is correct
31	Correct	946 ms	52956 KB	Output is correct
32	Correct	818 ms	42756 KB	Output is correct
33	Correct	546 ms	38636 KB	Output is correct
34	Correct	610 ms	38764 KB	Output is correct
35	Correct	824 ms	54108 KB	Output is correct
36	Correct	332 ms	37520 KB	Output is correct
37	Correct	621 ms	39532 KB	Output is correct
38	Correct	433 ms	37484 KB	Output is correct
39	Correct	658 ms	40428 KB	Output is correct
40	Correct	619 ms	38560 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	34412 KB	Output is correct
2	Correct	23 ms	34540 KB	Output is correct
3	Correct	22 ms	34412 KB	Output is correct
4	Correct	23 ms	34412 KB	Output is correct
5	Correct	23 ms	34540 KB	Output is correct
6	Correct	22 ms	34412 KB	Output is correct
7	Correct	22 ms	34412 KB	Output is correct
8	Correct	22 ms	34412 KB	Output is correct
9	Correct	22 ms	34412 KB	Output is correct
10	Correct	23 ms	34540 KB	Output is correct
11	Runtime error	297 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	23 ms	34412 KB	Output is correct
2	Correct	23 ms	34540 KB	Output is correct
3	Correct	22 ms	34412 KB	Output is correct
4	Correct	23 ms	34412 KB	Output is correct
5	Correct	23 ms	34540 KB	Output is correct
6	Correct	22 ms	34412 KB	Output is correct
7	Correct	22 ms	34412 KB	Output is correct
8	Correct	22 ms	34412 KB	Output is correct
9	Correct	22 ms	34412 KB	Output is correct
10	Correct	23 ms	34540 KB	Output is correct
11	Correct	504 ms	39148 KB	Output is correct
12	Correct	504 ms	38252 KB	Output is correct
13	Correct	463 ms	37612 KB	Output is correct
14	Correct	497 ms	37612 KB	Output is correct
15	Correct	514 ms	39020 KB	Output is correct
16	Correct	538 ms	38124 KB	Output is correct
17	Correct	539 ms	38380 KB	Output is correct
18	Correct	454 ms	40044 KB	Output is correct
19	Correct	350 ms	36844 KB	Output is correct
20	Correct	514 ms	39044 KB	Output is correct
21	Correct	608 ms	39532 KB	Output is correct
22	Correct	624 ms	39916 KB	Output is correct
23	Correct	627 ms	40300 KB	Output is correct
24	Correct	611 ms	38252 KB	Output is correct
25	Correct	761 ms	46956 KB	Output is correct
26	Correct	766 ms	46316 KB	Output is correct
27	Correct	798 ms	54380 KB	Output is correct
28	Correct	526 ms	41836 KB	Output is correct
29	Correct	432 ms	37868 KB	Output is correct
30	Correct	637 ms	40640 KB	Output is correct
31	Correct	946 ms	52956 KB	Output is correct
32	Correct	818 ms	42756 KB	Output is correct
33	Correct	546 ms	38636 KB	Output is correct
34	Correct	610 ms	38764 KB	Output is correct
35	Correct	824 ms	54108 KB	Output is correct
36	Correct	332 ms	37520 KB	Output is correct
37	Correct	621 ms	39532 KB	Output is correct
38	Correct	433 ms	37484 KB	Output is correct
39	Correct	658 ms	40428 KB	Output is correct
40	Correct	619 ms	38560 KB	Output is correct
41	Runtime error	297 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

답안 #329328

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