oj.uz

Submission #1094863

# Submission time Handle Problem Language Result Execution time Memory
1094863 2024-09-30T17:10:02 Z cpptowin Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 616 ms 49280 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
vi aa,bb,cc;
int n,q,a[maxn],sub[maxn],super[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    int m = (1 << n) - 1;
    fo(i,0,m)
    {
        char t;
        cin >> t;
        a[i] = t - '0';
        sub[i] = a[i];
        super[i] = a[i];
    }
    fo(i,0,n - 1) fod(mask,m,0) if(!bit(mask,i)) super[mask] += super[offbit(mask,i)];
    fo(i,0,n - 1) fo(mask,0,m) if(bit(mask,i)) sub[mask] += sub[offbit(mask,i)];
    while(q--)
    {
        string s;
        cin >> s;
        reverse(all(s));
        aa.clear();
        bb.clear();
        cc.clear();
        fo(i,0,ss(s) - 1) 
        {
            if(s[i] == '0') aa.pb(i);
            else if(s[i] == '1') bb.pb(i);
            else if(s[i] == '?') cc.pb(i);
        }
        int ans = 0;
        if(ss(cc) <= 6)
        {
            int vv = 0;
            for(int it : bb) vv = onbit(vv,it);
            fo(mask,0,(1 << ss(cc)) - 1)
            {
                int v1 = vv;
                fo(i,0,ss(cc) - 1) if(bit(mask,i)) 
                {
                    v1 = onbit(v1,cc[i]);
                }
                ans += a[v1];
            }
        }
        else if(ss(aa) <= 6)
        {
            int vv = 0;
            for(int it : bb) vv = onbit(vv,it);
            fo(mask,0,(1 << ss(aa)) - 1)
            {
                int v1 = vv;
                fo(i,0,ss(aa) - 1) if(bit(mask,i))
                {
                    v1 = onbit(v1,aa[i]);
                }
                if(bitcount(mask) & 1) ans -= super[v1];
                else ans += super[v1];
            }
        }
        else if(ss(bb) <= 6)
        {
            int vv = 0;
            for(int it : cc) vv = onbit(vv,it);
            fo(mask,0,(1 << ss(bb)) - 1)
            {
                int v1 = vv;
                fo(i,0,ss(bb) - 1) if(bit(mask,i))
                {
                    v1 = onbit(v1,bb[i]);
                }
                if(bitcount(mask) % 2 == ss(bb) % 2) ans += sub[v1];
                else ans -= sub[v1];
            }
        }
        cout << ans;en;
    }
}

Compilation message

snake_escaping.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main()
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 520 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 520 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 280 ms 15188 KB Output is correct
12 Correct 330 ms 14676 KB Output is correct
13 Correct 201 ms 14032 KB Output is correct
14 Correct 184 ms 14072 KB Output is correct
15 Correct 546 ms 15184 KB Output is correct
16 Correct 283 ms 14392 KB Output is correct
17 Correct 272 ms 14416 KB Output is correct
18 Correct 114 ms 16212 KB Output is correct
19 Correct 143 ms 13140 KB Output is correct
20 Correct 327 ms 14852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 520 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 280 ms 15188 KB Output is correct
12 Correct 330 ms 14676 KB Output is correct
13 Correct 201 ms 14032 KB Output is correct
14 Correct 184 ms 14072 KB Output is correct
15 Correct 546 ms 15184 KB Output is correct
16 Correct 283 ms 14392 KB Output is correct
17 Correct 272 ms 14416 KB Output is correct
18 Correct 114 ms 16212 KB Output is correct
19 Correct 143 ms 13140 KB Output is correct
20 Correct 327 ms 14852 KB Output is correct
21 Correct 177 ms 18512 KB Output is correct
22 Correct 528 ms 18516 KB Output is correct
23 Correct 297 ms 17464 KB Output is correct
24 Correct 252 ms 17236 KB Output is correct
25 Correct 218 ms 19284 KB Output is correct
26 Correct 375 ms 17748 KB Output is correct
27 Correct 355 ms 17744 KB Output is correct
28 Correct 131 ms 20176 KB Output is correct
29 Correct 168 ms 16132 KB Output is correct
30 Correct 343 ms 18260 KB Output is correct
31 Correct 616 ms 18256 KB Output is correct
32 Correct 316 ms 18256 KB Output is correct
33 Correct 200 ms 17160 KB Output is correct
34 Correct 249 ms 17220 KB Output is correct
35 Correct 365 ms 17748 KB Output is correct
36 Correct 126 ms 16132 KB Output is correct
37 Correct 556 ms 18264 KB Output is correct
38 Correct 196 ms 16212 KB Output is correct
39 Correct 286 ms 17404 KB Output is correct
40 Correct 255 ms 17236 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 520 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Runtime error 34 ms 49280 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 520 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 280 ms 15188 KB Output is correct
12 Correct 330 ms 14676 KB Output is correct
13 Correct 201 ms 14032 KB Output is correct
14 Correct 184 ms 14072 KB Output is correct
15 Correct 546 ms 15184 KB Output is correct
16 Correct 283 ms 14392 KB Output is correct
17 Correct 272 ms 14416 KB Output is correct
18 Correct 114 ms 16212 KB Output is correct
19 Correct 143 ms 13140 KB Output is correct
20 Correct 327 ms 14852 KB Output is correct
21 Correct 177 ms 18512 KB Output is correct
22 Correct 528 ms 18516 KB Output is correct
23 Correct 297 ms 17464 KB Output is correct
24 Correct 252 ms 17236 KB Output is correct
25 Correct 218 ms 19284 KB Output is correct
26 Correct 375 ms 17748 KB Output is correct
27 Correct 355 ms 17744 KB Output is correct
28 Correct 131 ms 20176 KB Output is correct
29 Correct 168 ms 16132 KB Output is correct
30 Correct 343 ms 18260 KB Output is correct
31 Correct 616 ms 18256 KB Output is correct
32 Correct 316 ms 18256 KB Output is correct
33 Correct 200 ms 17160 KB Output is correct
34 Correct 249 ms 17220 KB Output is correct
35 Correct 365 ms 17748 KB Output is correct
36 Correct 126 ms 16132 KB Output is correct
37 Correct 556 ms 18264 KB Output is correct
38 Correct 196 ms 16212 KB Output is correct
39 Correct 286 ms 17404 KB Output is correct
40 Correct 255 ms 17236 KB Output is correct
41 Runtime error 34 ms 49280 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -