oj.uz

Submission #719199

# Submission time Handle Problem Language Result Execution time Memory
719199 2023-04-05T16:05:12 Z ssense Snake Escaping (JOI18_snake_escaping) C++14
65 / 100
 2000 ms 20300 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 super[(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;
}

int answer_A(string t)
{
    vector<int> pos;
    int base = 0;
    for(int i = 0; i < n; i++)
    {
        if(t[i] == '0')
        {
            pos.pb(i);
        }
        if(t[i] == '1')
        {
            base+=1<<i;
        }
    }
    int sum = 0;
    int sz = pos.size();
    for(int mask = 0; mask < 1<<sz; mask++)
    {
        int now = base;
        for(int i = 0; i < pos.size(); i++)
        {
            if(mask & (1<<i))
            {
                now+=1<<pos[i];
            }
        }
        sum+=super[now]*power(-1, __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');
        super[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)];
            }
        }
    }
    for(int i = n-1; i >= 0; i--)
    {
        for(int mask = (1<<n)-1; mask >= 0; mask--)
        {
            if(!(mask&(1<<i)))
            {
                super[mask]+=super[mask^(1<<i)];
            }
        }
    }
    while(q--)
    {
        string t;
        cin >> t;
        reverse(all(t));
        int qm = 0, ones = 0, zeros = 0;
        for(int i = 0; i < n; i++)
        {
            if(t[i] == '?'){qm++;}
            if(t[i] == '1'){ones++;}
            if(t[i] == '0'){zeros++;}
        }
        //cout << answer_A(t) << endl;
        if(ones <= 6)
        {
            cout << answer_B(t) << endl;
        }
        else if(qm <= 6)
        {
            cout << answer_C(t, qm) << endl;
        }
        else
        {
            cout << answer_A(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:75: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]
   75 |         for(int i = 0; i < pos.size(); i++)
      |                        ~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'long long int answer_A(std::string)':
snake_escaping.cpp:107: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]
  107 |         for(int i = 0; i < pos.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 340 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #2
7.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 340 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1077 ms 4412 KB Output is correct
12 Correct 294 ms 3916 KB Output is correct
13 Correct 463 ms 3156 KB Output is correct
14 Correct 469 ms 3352 KB Output is correct
15 Correct 390 ms 4364 KB Output is correct
16 Correct 749 ms 3532 KB Output is correct
17 Correct 716 ms 3436 KB Output is correct
18 Correct 195 ms 5380 KB Output is correct
19 Correct 1061 ms 2272 KB Output is correct
20 Correct 1098 ms 4440 KB Output is correct

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 340 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1077 ms 4412 KB Output is correct
12 Correct 294 ms 3916 KB Output is correct
13 Correct 463 ms 3156 KB Output is correct
14 Correct 469 ms 3352 KB Output is correct
15 Correct 390 ms 4364 KB Output is correct
16 Correct 749 ms 3532 KB Output is correct
17 Correct 716 ms 3436 KB Output is correct
18 Correct 195 ms 5380 KB Output is correct
19 Correct 1061 ms 2272 KB Output is correct
20 Correct 1098 ms 4440 KB Output is correct
21 Execution timed out 2061 ms 17464 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
53.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 340 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 81 ms 18084 KB Output is correct
12 Correct 76 ms 18792 KB Output is correct
13 Correct 141 ms 20072 KB Output is correct
14 Correct 210 ms 20076 KB Output is correct
15 Correct 99 ms 20204 KB Output is correct
16 Correct 219 ms 20076 KB Output is correct
17 Correct 192 ms 20212 KB Output is correct
18 Correct 65 ms 20300 KB Output is correct
19 Correct 74 ms 19912 KB Output is correct
20 Correct 101 ms 20172 KB Output is correct
21 Correct 148 ms 20152 KB Output is correct
22 Correct 201 ms 20128 KB Output is correct
23 Correct 148 ms 20040 KB Output is correct
24 Correct 300 ms 20108 KB Output is correct
25 Correct 214 ms 20140 KB Output is correct
26 Correct 73 ms 20024 KB Output is correct
27 Correct 87 ms 20124 KB Output is correct
28 Correct 93 ms 19916 KB Output is correct
29 Correct 195 ms 20208 KB Output is correct
30 Correct 319 ms 20180 KB Output is correct
31 Correct 95 ms 20044 KB Output is correct
32 Correct 215 ms 20144 KB Output is correct
33 Correct 189 ms 20080 KB Output is correct
34 Correct 66 ms 19912 KB Output is correct
35 Correct 152 ms 20200 KB Output is correct
36 Correct 153 ms 20036 KB Output is correct
37 Correct 161 ms 20068 KB Output is correct
38 Correct 150 ms 20136 KB Output is correct
39 Correct 156 ms 20088 KB Output is correct
40 Correct 150 ms 20044 KB Output is correct

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 340 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1077 ms 4412 KB Output is correct
12 Correct 294 ms 3916 KB Output is correct
13 Correct 463 ms 3156 KB Output is correct
14 Correct 469 ms 3352 KB Output is correct
15 Correct 390 ms 4364 KB Output is correct
16 Correct 749 ms 3532 KB Output is correct
17 Correct 716 ms 3436 KB Output is correct
18 Correct 195 ms 5380 KB Output is correct
19 Correct 1061 ms 2272 KB Output is correct
20 Correct 1098 ms 4440 KB Output is correct
21 Execution timed out 2061 ms 17464 KB Time limit exceeded
22 Halted 0 ms 0 KB -