oj.uz

Submission #1099128

# Submission time Handle Problem Language Result Execution time Memory
1099128 2024-10-10T15:31:31 Z Phuoc Snake Escaping (JOI18_snake_escaping) C++14
12 / 100
 465 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

#define el '\n';
#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b) {a = b; return true;} return false;
    }

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }

const int MOD = (int)1e9 + 7;

template <class T1, class T2> 
    void add (T1 &a, T2 b) {
        a += b;
        if (a >= MOD) a -= MOD;
    }

const int N = 50100;
const int oo = (int)1e9 + 7;
const ll INF = (ll)1e18 + 9LL;
const int LOG = 22;

int nSeg, nQuery;
string toxicity;

void init (void) {
    cin >> nSeg >> nQuery >> toxicity;
}

namespace subtask1 {
    bool ok (void) {
        return nSeg <= 10 && nQuery <= 1000;
    }

    long long res = 0;

    void Try (string s, int i, int mask) {
        if(i >= s.size()) {
            res += (toxicity[mask] - '0');
            return;
        }
        long long res = 0;
        if(s[i] != '?') {
            Try (s, i + 1, mask + (s[i] - '0') * MASK(i));
        }
        else {
            Try (s, i + 1, mask + MASK(i));
            Try (s, i + 1, mask);
        }
    }

    void solve (void) {
        for (int i = 1; i <= nQuery; i++) {
            string s; cin >> s;
            reverse(s.begin(), s.end());
            Try (s, 0, 0);
            cout << res << el;
            res = 0;
        }
    }
}

namespace subtask2 {
    bool ok (void) {
        return nSeg <= 13;
    }

    vector <string> pattern;

    void gen_pattern (int i, string s) {
        if(i >= nSeg) {
            pattern.push_back(s);
            return;
        }
        gen_pattern (i + 1, s + '0');
        gen_pattern (i + 1, s + '1');
        gen_pattern (i + 1, s + '?');
    }

    long long res = 0;

    void Try (string s, int i, int mask) {
        if(i >= s.size()) {
            res += (toxicity[mask] - '0');
            return;
        }
        if(s[i] != '?') {
            Try (s, i + 1, mask + (s[i] - '0') * MASK(i));
        }
        else {
            Try (s, i + 1, mask + MASK(i));
            Try (s, i + 1, mask);
        }
    }

    map <string, long long> ans;

    void solve (void) {
        gen_pattern(0, "");
        for (int i = 0; i < pattern.size(); i++) {
            Try (pattern[i], 0, 0);
            ans[pattern[i]] = res;
            // cout << pattern[i] << ' << el;
            res = 0;
        }

        for (int i = 1; i <= nQuery; i++) {
            string s; cin >> s;
            reverse(s.begin(), s.end());
            cout << ans[s] << el;
        }
    }
}

void solve (void) { 
    if(subtask1::ok()) {subtask1::solve(); return;}
    if(subtask2::ok()) {subtask2::solve(); return;}
}

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

    int ntest = 1; 

    while(ntest--) {
        init();
        solve();
    }
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void subtask1::Try(std::string, int, int)':
snake_escaping.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(i >= s.size()) {
      |            ~~^~~~~~~~~~~
snake_escaping.cpp:54:19: warning: unused variable 'res' [-Wunused-variable]
   54 |         long long res = 0;
      |                   ^~~
snake_escaping.cpp: In function 'void subtask2::Try(std::string, int, int)':
snake_escaping.cpp:95:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         if(i >= s.size()) {
      |            ~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask2::solve()':
snake_escaping.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int i = 0; i < pattern.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 468 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 468 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 352 ms 21800 KB Output is correct
12 Correct 334 ms 21220 KB Output is correct
13 Correct 465 ms 20552 KB Output is correct
14 Correct 418 ms 20636 KB Output is correct
15 Correct 382 ms 21448 KB Output is correct
16 Correct 441 ms 20712 KB Output is correct
17 Correct 456 ms 20796 KB Output is correct
18 Correct 290 ms 22468 KB Output is correct
19 Correct 303 ms 19500 KB Output is correct
20 Correct 319 ms 21316 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 468 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 352 ms 21800 KB Output is correct
12 Correct 334 ms 21220 KB Output is correct
13 Correct 465 ms 20552 KB Output is correct
14 Correct 418 ms 20636 KB Output is correct
15 Correct 382 ms 21448 KB Output is correct
16 Correct 441 ms 20712 KB Output is correct
17 Correct 456 ms 20796 KB Output is correct
18 Correct 290 ms 22468 KB Output is correct
19 Correct 303 ms 19500 KB Output is correct
20 Correct 319 ms 21316 KB Output is correct
21 Runtime error 76 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 468 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Incorrect 3 ms 3828 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 18 ms 468 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 352 ms 21800 KB Output is correct
12 Correct 334 ms 21220 KB Output is correct
13 Correct 465 ms 20552 KB Output is correct
14 Correct 418 ms 20636 KB Output is correct
15 Correct 382 ms 21448 KB Output is correct
16 Correct 441 ms 20712 KB Output is correct
17 Correct 456 ms 20796 KB Output is correct
18 Correct 290 ms 22468 KB Output is correct
19 Correct 303 ms 19500 KB Output is correct
20 Correct 319 ms 21316 KB Output is correct
21 Runtime error 76 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -