oj.uz

Submission #160789

# Submission time Handle Problem Language Result Execution time Memory
160789 2019-10-30T01:10:44 Z combi1k1 Dango Maker (JOI18_dango_maker) C++14
0 / 100
 2 ms 376 KB 
#include<bits/stdc++.h>

using namespace std;

int8_t  c[1 << 20];
string  s;

int f0[1 << 20];
int f1[1 << 20];

int work()  {
    int m0 = 0;
    int m1 = 0;
    int m2 = 0;

    int L = s.size();

    reverse(s.begin(),s.end());

    for(int i = 0 ; i < L ; ++i)    {
        if (s[i] == '0')    m0 |= (1 << i);
        if (s[i] == '1')    m1 |= (1 << i);
        if (s[i] == '?')    m2 |= (1 << i);
    }

    if (__builtin_popcount(m0) <= L / 3)    {
        int ans = f1[m1];
        for(int x = m0 ; x ; x = (x - 1) & m0)  {
            if (__builtin_popcount(x) & 1)
                ans -= f1[m1 | x];
            else
                ans += f1[m1 | x];
        }
        return  ans;
    }
    if (__builtin_popcount(m1) <= L / 3)    {
        int ans = f0[m0];
        for(int x = m1 ; x ; x = (x - 1) & m1)  {
            if (__builtin_popcount(x) & 1)
                ans -= f0[m0 | x];
            else
                ans += f0[m0 | x];
        }
        return  ans;
    }
    if (__builtin_popcount(m2) <= L / 3)    {
        int ans = c[m0 | m1];
        for(int x = m2 ; x ; x = (x - 1) & m0)
            ans += c[m0 | m1 | x];

        return  ans;
    }
}

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

    int n;  cin >> n;
    int q;  cin >> q;

    int m = (1 << n);

    cin >> s;

    for(int i = 0 ; i < m ; ++i)
        c[i] = s[i] - '0',
        f0[m - i - 1] = f1[i] = c[i];
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    if (j >> i & 1)
        f0[j ^ (1 << i)] += f0[j],
        f1[j ^ (1 << i)] += f1[j];

    for(int i = 0 ; i < q ; ++i)    {
        cin >> s;
        cout << work() << "\n";
    }
}

Compilation message

dango_maker.cpp: In function 'int work()':
dango_maker.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 13.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 67.0

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