oj.uz

Submission #719187

# Submission time Handle Problem Language Result Execution time Memory
719187 2023-04-05T15:27:01 Z ssense Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 16072 KB 
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);}int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}//mesanu

int n, q;
string s;

int answer_C(string t, int qm)
{
    int sum = 0;
    for(int i = 0; i < 1<<qm; i++)
    {
        int now = 0;
        int idx = 0;
        for(int j = 0; j < n; j++)
        {
            if(t[j] == '1')
            {
                now+=1<<j;
            }
            if(t[j] == '?')
            {
                if(i & (1<<idx))
                {
                    now+=1<<j;
                }
                idx++;
            }
        }
        sum+=(s[now]-'0');
    }
    return sum;
}

int sub[(1<<20)+5];

int answer_B(string t)
{
    vector<int> pos;
    int base = 0;
    for(int i = 0; i < n; i++)
    {
        if(t[i] == '1')
        {
            pos.pb(i);
        }
        if(t[i] == '?')
        {
            base+=1<<i;
        }
    }
    int sum = 0;
    int sz = pos.size();
    for(int mask = (1<<sz)-1; mask >= 0; mask--)
    {
        int now = base;
        for(int i = 0; i < pos.size(); i++)
        {
            if(mask & (1<<i))
            {
                now+=1<<pos[i];
            }
        }
        sum+=sub[now]*power(-1, sz-__builtin_popcount(mask), MOD);
    }
    return sum;
}

void solve()
{
    cin >> n >> q;
    cin >> s;
    for(int i = 0; i < 1<<n; i++)
    {
        sub[i] = (s[i]-'0');
    }
    for(int i = 0; i < n; i++)
    {
        for(int mask = 0; mask < 1<< n; mask++)
        {
            if(mask & 1<<i)
            {
                sub[mask]+=sub[mask^(1<<i)];
            }
        }
    }
    while(q--)
    {
        string t;
        cin >> t;
        reverse(all(t));
        int qm = 0;
        for(int i = 0; i < t.size(); i++)
        {
            if(t[i] == '?'){qm++;}
        }
        //cout << answer_C(t, qm) << endl;
        cout << answer_B(t) << endl;
    }
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
/*
3 5
12345678
000
0??
1?0
?11
???
*/

Compilation message

snake_escaping.cpp: In function 'long long int answer_B(std::string)':
snake_escaping.cpp:74:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i = 0; i < pos.size(); i++)
      |                        ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:110:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int i = 0; i < t.size(); i++)
      |                        ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 962 ms 8180 KB Output is correct
12 Correct 254 ms 14676 KB Output is correct
13 Correct 440 ms 13912 KB Output is correct
14 Correct 450 ms 14036 KB Output is correct
15 Correct 366 ms 15028 KB Output is correct
16 Correct 713 ms 14280 KB Output is correct
17 Correct 775 ms 14144 KB Output is correct
18 Correct 189 ms 16072 KB Output is correct
19 Correct 936 ms 13092 KB Output is correct
20 Execution timed out 2079 ms 14340 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 962 ms 8180 KB Output is correct
12 Correct 254 ms 14676 KB Output is correct
13 Correct 440 ms 13912 KB Output is correct
14 Correct 450 ms 14036 KB Output is correct
15 Correct 366 ms 15028 KB Output is correct
16 Correct 713 ms 14280 KB Output is correct
17 Correct 775 ms 14144 KB Output is correct
18 Correct 189 ms 16072 KB Output is correct
19 Correct 936 ms 13092 KB Output is correct
20 Execution timed out 2079 ms 14340 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Execution timed out 2029 ms 11888 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 962 ms 8180 KB Output is correct
12 Correct 254 ms 14676 KB Output is correct
13 Correct 440 ms 13912 KB Output is correct
14 Correct 450 ms 14036 KB Output is correct
15 Correct 366 ms 15028 KB Output is correct
16 Correct 713 ms 14280 KB Output is correct
17 Correct 775 ms 14144 KB Output is correct
18 Correct 189 ms 16072 KB Output is correct
19 Correct 936 ms 13092 KB Output is correct
20 Execution timed out 2079 ms 14340 KB Time limit exceeded
21 Halted 0 ms 0 KB -