oj.uz

Submission #535728

# Submission time Handle Problem Language Result Execution time Memory
535728 2022-03-11T03:47:20 Z sare Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 212 KB 
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
    string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += to_string(x);
    }
    res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
    return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()

const int MAXN = 20, MAXQ = 1e6;
int l, q, dp[2][1 << MAXN];
char s[MAXN], t[MAXN];
 
int main() {
    scanf("%d%d%s", &l, &q, s);
    for (int i = 0; i < (1 << l); i++) {
        dp[0][i] = dp[1][i] = s[i] - '0';
    }
    for (int k = 0; k < l; k++) {
        for (int i = 0; i < (1 << l); i++) {
            if (i >> k & 1) {
                dp[0][i] += dp[0][i ^ (1 << k)];
            }
            else {
                dp[1][i] += dp[1][i ^ (1 << k)];
            }
        }
    }
    while(q--) {
        int n[3] = {}, mask[3] = {};
        scanf("%s", t);
        for (int i = 0; i < l; i++) {
            if (t[i] == '?') {
                n[2]++;
                mask[2] ^= 1 << (l - i - 1);
            }
            else {
                n[t[i] - '0']++;
                mask[t[i] - '0'] ^= 1 << (l - i - 1);
            }
        }
        wis(n[0], n[1], n[2], mask[0], mask[1], mask[2]);
        int ans = 0;
        if (n[2] <= min(n[0], n[1])) {
            for (int sub = mask[2]; sub; sub = (sub - 1) & mask[2]) {
                ans += s[sub | mask[1]] - '0';
            }
            ans += s[mask[1]] - '0';
        }
        else if (n[1] <= n[0]) {
            for (int sub = mask[1]; sub; sub = (sub - 1) & mask[1]) {
                ans += dp[0][sub ^ mask[1] ^ mask[2]] * (__builtin_popcount(sub) % 2 ? -1 : 1);
            } 
            ans += dp[0][mask[1] ^ mask[2]];
        }
        else {
            for (int sub = mask[0]; sub; sub = (sub - 1) & mask[0]) {
                ans += dp[1][((1 << l) - 1) ^ sub ^ mask[0] ^ mask[2]] * (__builtin_popcount(sub) % 2 ? -1 : 1);
            }
            ans += dp[1][((1 << l) - 1) ^ mask[0] ^ mask[2]];
        }
        printf("%d\n", ans);
    }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:34:18: warning: statement has no effect [-Wunused-value]
   34 | #define wis(...) 0
      |                  ^
snake_escaping.cpp:72:9: note: in expansion of macro 'wis'
   72 |         wis(n[0], n[1], n[2], mask[0], mask[1], mask[2]);
      |         ^~~
snake_escaping.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d%s", &l, &q, s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%s", t);
      |         ~~~~~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -