oj.uz

Submission #329322

# Submission time Handle Problem Language Result Execution time Memory
329322 2020-11-20T14:56:02 Z HoneyBadger Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 592 ms 26348 KB 
#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>


/*
#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;


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


int n, q;
int pw3[14];
int dp[1600000]; //3**13
int a[1 << 13];

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

    pw3[0] = 1;
    fi(1, 14) pw3[i] = pw3[i - 1] * 3;

    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i) {
    	char c;
    	cin >> c;
    	a[i] = c - '0';
    }
    for (int mask = 0; mask < pw3[n]; ++mask) {
    	int cur = mask;
    	int mask2 = 0;
    	int pos3 = -1;
    	for (int it = 0; it < n; ++it) {
    		if (cur % 3 == 2) {
    			pos3 = it;
    		}  else if (cur % 3 == 1) {
    			mask2 += 1 << it;
    		}
    		cur /= 3;
    	}
    	if (pos3 == -1) {
    		dp[mask] = a[mask2];
    	} else {
    		dp[mask] = dp[mask - pw3[pos3]] + dp[mask - 2 * pw3[pos3]];
    	}
    }
    while (q--) {
    	int x = 0;
    	fi(0, n) {
    		char c;
    		cin >> c;
    		if (c == '1') x += pw3[n - i - 1];
    		if (c == '?') x += 2 * pw3[n - i - 1]; 
    	}
    	cout << dp[x] << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 325 ms 4716 KB Output is correct
12 Correct 330 ms 4352 KB Output is correct
13 Correct 345 ms 3712 KB Output is correct
14 Correct 347 ms 3692 KB Output is correct
15 Correct 331 ms 4588 KB Output is correct
16 Correct 376 ms 3820 KB Output is correct
17 Correct 364 ms 3948 KB Output is correct
18 Correct 257 ms 5868 KB Output is correct
19 Correct 329 ms 2668 KB Output is correct
20 Correct 330 ms 4332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 325 ms 4716 KB Output is correct
12 Correct 330 ms 4352 KB Output is correct
13 Correct 345 ms 3712 KB Output is correct
14 Correct 347 ms 3692 KB Output is correct
15 Correct 331 ms 4588 KB Output is correct
16 Correct 376 ms 3820 KB Output is correct
17 Correct 364 ms 3948 KB Output is correct
18 Correct 257 ms 5868 KB Output is correct
19 Correct 329 ms 2668 KB Output is correct
20 Correct 330 ms 4332 KB Output is correct
21 Correct 462 ms 10988 KB Output is correct
22 Correct 476 ms 11244 KB Output is correct
23 Correct 547 ms 10220 KB Output is correct
24 Correct 553 ms 10020 KB Output is correct
25 Correct 470 ms 12140 KB Output is correct
26 Correct 577 ms 10732 KB Output is correct
27 Correct 587 ms 24048 KB Output is correct
28 Correct 378 ms 26348 KB Output is correct
29 Correct 454 ms 22472 KB Output is correct
30 Correct 467 ms 24680 KB Output is correct
31 Correct 547 ms 24428 KB Output is correct
32 Correct 576 ms 24556 KB Output is correct
33 Correct 512 ms 23244 KB Output is correct
34 Correct 589 ms 23404 KB Output is correct
35 Correct 592 ms 24044 KB Output is correct
36 Correct 364 ms 22380 KB Output is correct
37 Correct 465 ms 24588 KB Output is correct
38 Correct 458 ms 22508 KB Output is correct
39 Correct 585 ms 23780 KB Output is correct
40 Correct 568 ms 23404 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Runtime error 25 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 325 ms 4716 KB Output is correct
12 Correct 330 ms 4352 KB Output is correct
13 Correct 345 ms 3712 KB Output is correct
14 Correct 347 ms 3692 KB Output is correct
15 Correct 331 ms 4588 KB Output is correct
16 Correct 376 ms 3820 KB Output is correct
17 Correct 364 ms 3948 KB Output is correct
18 Correct 257 ms 5868 KB Output is correct
19 Correct 329 ms 2668 KB Output is correct
20 Correct 330 ms 4332 KB Output is correct
21 Correct 462 ms 10988 KB Output is correct
22 Correct 476 ms 11244 KB Output is correct
23 Correct 547 ms 10220 KB Output is correct
24 Correct 553 ms 10020 KB Output is correct
25 Correct 470 ms 12140 KB Output is correct
26 Correct 577 ms 10732 KB Output is correct
27 Correct 587 ms 24048 KB Output is correct
28 Correct 378 ms 26348 KB Output is correct
29 Correct 454 ms 22472 KB Output is correct
30 Correct 467 ms 24680 KB Output is correct
31 Correct 547 ms 24428 KB Output is correct
32 Correct 576 ms 24556 KB Output is correct
33 Correct 512 ms 23244 KB Output is correct
34 Correct 589 ms 23404 KB Output is correct
35 Correct 592 ms 24044 KB Output is correct
36 Correct 364 ms 22380 KB Output is correct
37 Correct 465 ms 24588 KB Output is correct
38 Correct 458 ms 22508 KB Output is correct
39 Correct 585 ms 23780 KB Output is correct
40 Correct 568 ms 23404 KB Output is correct
41 Runtime error 25 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -