oj.uz

Submission #357650

# Submission time Handle Problem Language Result Execution time Memory
357650 2021-01-24T10:38:06 Z cute_hater Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 21064 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#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")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

map <string, int> cnt;
string t;

void calc(int l, string & s) {
    int ans = 0;
    loop(i, (1ll << l)) {
        bool f = 1;
        loop(bit, l)
            if (t[bit] != '?' && bool(i & (1ll << bit)) != t[bit] - '0') {
                f = 0; break;
            }
        if (f)
            ans += s[i] - '0';
    }
    cnt[t] = ans;
}

void precalc(int l, string &s) {
    if (t.size() == l) {
        calc(l, s);
        return;
    }
    t.pb('0');
    precalc(l, s);
    t[t.size() - 1] = '1';
    precalc(l, s);
    t[t.size() - 1] = '?';
    precalc(l, s);
    t.pop_back();
}

void solve() {
    int l, q;
    string s;
    cin >> l >> q >> s;
    precalc(l, s);
    loop(i, q) {
        string t; cin >> t;
        reverse(all(t));
        cout << cnt[t] << "\n";
    }
}


signed main() {
    //freopen("b2.txt", "r", stdin);
    //freopen("ans9.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void precalc(ll, std::string&)':
snake_escaping.cpp:70:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   70 |     if (t.size() == l) {
      |         ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4972 KB Output is correct
2 Correct 322 ms 5100 KB Output is correct
3 Correct 310 ms 5100 KB Output is correct
4 Correct 306 ms 4992 KB Output is correct
5 Correct 314 ms 4972 KB Output is correct
6 Correct 311 ms 5100 KB Output is correct
7 Correct 306 ms 4972 KB Output is correct
8 Correct 307 ms 5100 KB Output is correct
9 Correct 305 ms 4972 KB Output is correct
10 Correct 312 ms 4972 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4972 KB Output is correct
2 Correct 322 ms 5100 KB Output is correct
3 Correct 310 ms 5100 KB Output is correct
4 Correct 306 ms 4992 KB Output is correct
5 Correct 314 ms 4972 KB Output is correct
6 Correct 311 ms 5100 KB Output is correct
7 Correct 306 ms 4972 KB Output is correct
8 Correct 307 ms 5100 KB Output is correct
9 Correct 305 ms 4972 KB Output is correct
10 Correct 312 ms 4972 KB Output is correct
11 Correct 778 ms 16620 KB Output is correct
12 Correct 831 ms 19528 KB Output is correct
13 Correct 950 ms 18752 KB Output is correct
14 Correct 944 ms 18924 KB Output is correct
15 Correct 938 ms 19888 KB Output is correct
16 Correct 1000 ms 18924 KB Output is correct
17 Correct 1036 ms 18896 KB Output is correct
18 Correct 754 ms 21064 KB Output is correct
19 Correct 792 ms 17900 KB Output is correct
20 Correct 816 ms 19476 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4972 KB Output is correct
2 Correct 322 ms 5100 KB Output is correct
3 Correct 310 ms 5100 KB Output is correct
4 Correct 306 ms 4992 KB Output is correct
5 Correct 314 ms 4972 KB Output is correct
6 Correct 311 ms 5100 KB Output is correct
7 Correct 306 ms 4972 KB Output is correct
8 Correct 307 ms 5100 KB Output is correct
9 Correct 305 ms 4972 KB Output is correct
10 Correct 312 ms 4972 KB Output is correct
11 Correct 778 ms 16620 KB Output is correct
12 Correct 831 ms 19528 KB Output is correct
13 Correct 950 ms 18752 KB Output is correct
14 Correct 944 ms 18924 KB Output is correct
15 Correct 938 ms 19888 KB Output is correct
16 Correct 1000 ms 18924 KB Output is correct
17 Correct 1036 ms 18896 KB Output is correct
18 Correct 754 ms 21064 KB Output is correct
19 Correct 792 ms 17900 KB Output is correct
20 Correct 816 ms 19476 KB Output is correct
21 Execution timed out 2082 ms 6728 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4972 KB Output is correct
2 Correct 322 ms 5100 KB Output is correct
3 Correct 310 ms 5100 KB Output is correct
4 Correct 306 ms 4992 KB Output is correct
5 Correct 314 ms 4972 KB Output is correct
6 Correct 311 ms 5100 KB Output is correct
7 Correct 306 ms 4972 KB Output is correct
8 Correct 307 ms 5100 KB Output is correct
9 Correct 305 ms 4972 KB Output is correct
10 Correct 312 ms 4972 KB Output is correct
11 Execution timed out 2086 ms 2440 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4972 KB Output is correct
2 Correct 322 ms 5100 KB Output is correct
3 Correct 310 ms 5100 KB Output is correct
4 Correct 306 ms 4992 KB Output is correct
5 Correct 314 ms 4972 KB Output is correct
6 Correct 311 ms 5100 KB Output is correct
7 Correct 306 ms 4972 KB Output is correct
8 Correct 307 ms 5100 KB Output is correct
9 Correct 305 ms 4972 KB Output is correct
10 Correct 312 ms 4972 KB Output is correct
11 Correct 778 ms 16620 KB Output is correct
12 Correct 831 ms 19528 KB Output is correct
13 Correct 950 ms 18752 KB Output is correct
14 Correct 944 ms 18924 KB Output is correct
15 Correct 938 ms 19888 KB Output is correct
16 Correct 1000 ms 18924 KB Output is correct
17 Correct 1036 ms 18896 KB Output is correct
18 Correct 754 ms 21064 KB Output is correct
19 Correct 792 ms 17900 KB Output is correct
20 Correct 816 ms 19476 KB Output is correct
21 Execution timed out 2082 ms 6728 KB Time limit exceeded
22 Halted 0 ms 0 KB -