oj.uz

Submission #619721

# Submission time Handle Problem Language Result Execution time Memory
619721 2022-08-02T15:07:58 Z Do_you_copy Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 17992 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 20;

int n, q;
string s, t;
int dp[(1 << maxN) + 2];
int f[(1 << maxN) + 2];
int cnt[(1 << maxN) + 2];

void WriteInt(int x)
{
    if (x > 9)
        WriteInt(x / 10);
    putchar(x % 10 + '0');
}

inline int inv(int i){
    return ((1 << n) - 1) ^ i;
}
void Init(){
    cin >> n >> q >> s;
    for (int i = 0; i < int(s.length()); ++i){
        dp[i] = s[i] - '0';
        f[inv(i)] = dp[i];
    }
    for (int i = 0; i < n; ++i){
        for (int j = 1; j < 1 << n; ++j){
            if (j & (1 << i)){
                dp[j] += dp[j ^ (1 << i)];
            }
        }
    }
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < 1 << n; ++j){
            if (j & (1 << i)){
                f[j] += f[j ^ (1 << i)];
            }
        }
    }
    for (int i = 1; i < 1 << n; ++i){
        int j = i & -i;
        cnt[i] = cnt[i ^ j] + 1;
    }
    while (q--){
        cin >> t;
        vector <int> A, B, C;
        vector <int> val((1 << n) + 1, 0);
        for (int i = 0; i < int(t.length()); ++i){
            if (t[i] == '0') A.pb(n - i - 1);
            if (t[i] == '1') B.pb(n - i - 1);
            if (t[i] == '?') C.pb(n - i - 1);
        }
        int x = A.size(), y = B.size(), z = C.size();
        if (x <= 6){
            int tem = 0, ans = 0;
            for (const int &i: C) tem += 1 << i;
            for (int i = 0; i < 1 << x; ++i){
                int t = i & -i;
                if (i != 0)
                val[i] = val[i ^ t] + (1 << A[__lg(t)]);
                if ((x & 1) ^ (cnt[i] & 1)) ans -= f[val[i] + tem];
                else ans += f[val[i] + tem];
            }
            WriteInt(ans);
            putchar('\n');
        }
        else if (y <= 6){
            int tem = 0, ans = 0;
            for (int i: C) tem += 1 << i;
            for (int i = 0; i < 1 << y; ++i){
                int t = i & -i;
                if (i != 0)
                val[i] = val[i ^ t] + (1 << B[__lg(t)]);
                if ((y & 1) ^ (cnt[i] & 1)) ans -= dp[val[i] + tem];
                else ans += dp[val[i] + tem];
            }
            WriteInt(ans);
            putchar('\n');
        }
        else{
            //brute all ?s
            for (int i = 1; i < 1 << z; ++i){
                int t = i & -i;
                val[i] = val[i ^ t] + (1 << C[__lg(t)]);
            }
            int tem = 0, ans = 0;
            for (const auto i: B) tem += 1 << i;
            for (int i = 0; i < 1 << z; ++i){
                ans += s[val[i] + tem] - '0';
            }
            WriteInt(ans);
            putchar('\n');
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 514 ms 4352 KB Output is correct
12 Correct 636 ms 3916 KB Output is correct
13 Correct 700 ms 3204 KB Output is correct
14 Correct 670 ms 3332 KB Output is correct
15 Correct 524 ms 4348 KB Output is correct
16 Correct 631 ms 3472 KB Output is correct
17 Correct 633 ms 3396 KB Output is correct
18 Correct 361 ms 5372 KB Output is correct
19 Correct 590 ms 2268 KB Output is correct
20 Correct 512 ms 4028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 514 ms 4352 KB Output is correct
12 Correct 636 ms 3916 KB Output is correct
13 Correct 700 ms 3204 KB Output is correct
14 Correct 670 ms 3332 KB Output is correct
15 Correct 524 ms 4348 KB Output is correct
16 Correct 631 ms 3472 KB Output is correct
17 Correct 633 ms 3396 KB Output is correct
18 Correct 361 ms 5372 KB Output is correct
19 Correct 590 ms 2268 KB Output is correct
20 Correct 512 ms 4028 KB Output is correct
21 Correct 1246 ms 4652 KB Output is correct
22 Correct 1339 ms 4712 KB Output is correct
23 Correct 1591 ms 3684 KB Output is correct
24 Correct 1409 ms 3564 KB Output is correct
25 Correct 1248 ms 5400 KB Output is correct
26 Correct 1379 ms 4048 KB Output is correct
27 Correct 1385 ms 4048 KB Output is correct
28 Correct 1119 ms 6476 KB Output is correct
29 Correct 1420 ms 2448 KB Output is correct
30 Correct 1221 ms 4600 KB Output is correct
31 Correct 1395 ms 4440 KB Output is correct
32 Correct 1405 ms 4504 KB Output is correct
33 Correct 1240 ms 3272 KB Output is correct
34 Correct 1388 ms 3556 KB Output is correct
35 Correct 1423 ms 3888 KB Output is correct
36 Correct 1070 ms 2528 KB Output is correct
37 Correct 1278 ms 4532 KB Output is correct
38 Correct 1368 ms 2544 KB Output is correct
39 Correct 1362 ms 3560 KB Output is correct
40 Correct 1444 ms 3508 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Execution timed out 2075 ms 17992 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 514 ms 4352 KB Output is correct
12 Correct 636 ms 3916 KB Output is correct
13 Correct 700 ms 3204 KB Output is correct
14 Correct 670 ms 3332 KB Output is correct
15 Correct 524 ms 4348 KB Output is correct
16 Correct 631 ms 3472 KB Output is correct
17 Correct 633 ms 3396 KB Output is correct
18 Correct 361 ms 5372 KB Output is correct
19 Correct 590 ms 2268 KB Output is correct
20 Correct 512 ms 4028 KB Output is correct
21 Correct 1246 ms 4652 KB Output is correct
22 Correct 1339 ms 4712 KB Output is correct
23 Correct 1591 ms 3684 KB Output is correct
24 Correct 1409 ms 3564 KB Output is correct
25 Correct 1248 ms 5400 KB Output is correct
26 Correct 1379 ms 4048 KB Output is correct
27 Correct 1385 ms 4048 KB Output is correct
28 Correct 1119 ms 6476 KB Output is correct
29 Correct 1420 ms 2448 KB Output is correct
30 Correct 1221 ms 4600 KB Output is correct
31 Correct 1395 ms 4440 KB Output is correct
32 Correct 1405 ms 4504 KB Output is correct
33 Correct 1240 ms 3272 KB Output is correct
34 Correct 1388 ms 3556 KB Output is correct
35 Correct 1423 ms 3888 KB Output is correct
36 Correct 1070 ms 2528 KB Output is correct
37 Correct 1278 ms 4532 KB Output is correct
38 Correct 1368 ms 2544 KB Output is correct
39 Correct 1362 ms 3560 KB Output is correct
40 Correct 1444 ms 3508 KB Output is correct
41 Execution timed out 2075 ms 17992 KB Time limit exceeded
42 Halted 0 ms 0 KB -