oj.uz

Submission #619714

# Submission time Handle Problem Language Result Execution time Memory
619714 2022-08-02T14:56:55 Z Do_you_copy Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 20140 KB 
#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];

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 (int i: C) tem += 1 << i;
            for (int i = 1; i < 1 << x; ++i){
                int t = i & -i;
                val[i] = val[i ^ t] + (1 << A[__lg(t)]);
            }
            for (int i = 0; i < 1 << x; ++i){
                if ((x & 1) ^ (cnt[i] & 1)) ans -= f[val[i] + tem];
                else ans += f[val[i] + tem];
            }
            cout << ans << "\n";
        }
        else if (y <= 6){
            int tem = 0, ans = 0;
            for (int i: C) tem += 1 << i;
            for (int i = 1; i < 1 << y; ++i){
                int t = i & -i;
                val[i] = val[i ^ t] + (1 << B[__lg(t)]);
            }
            for (int i = 0; i < 1 << y; ++i){
                if ((y & 1) ^ (cnt[i] & 1)) ans -= dp[val[i] + tem];
                else ans += dp[val[i] + tem];
            }
            cout << ans << "\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 (int i: B) tem += 1 << i;
            for (int i = 0; i < 1 << z; ++i){
                ans += s[val[i] + tem] - '0';
            }
            cout << ans << "\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:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         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 2 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 344 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 2 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 344 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 719 ms 15084 KB Output is correct
12 Correct 771 ms 14684 KB Output is correct
13 Correct 820 ms 14032 KB Output is correct
14 Correct 758 ms 14024 KB Output is correct
15 Correct 648 ms 15068 KB Output is correct
16 Correct 689 ms 14288 KB Output is correct
17 Correct 871 ms 14260 KB Output is correct
18 Correct 464 ms 16028 KB Output is correct
19 Correct 867 ms 13092 KB Output is correct
20 Correct 620 ms 14792 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 2 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 344 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 719 ms 15084 KB Output is correct
12 Correct 771 ms 14684 KB Output is correct
13 Correct 820 ms 14032 KB Output is correct
14 Correct 758 ms 14024 KB Output is correct
15 Correct 648 ms 15068 KB Output is correct
16 Correct 689 ms 14288 KB Output is correct
17 Correct 871 ms 14260 KB Output is correct
18 Correct 464 ms 16028 KB Output is correct
19 Correct 867 ms 13092 KB Output is correct
20 Correct 620 ms 14792 KB Output is correct
21 Correct 1362 ms 18168 KB Output is correct
22 Correct 1443 ms 18364 KB Output is correct
23 Correct 1834 ms 17368 KB Output is correct
24 Correct 1616 ms 17144 KB Output is correct
25 Correct 1485 ms 19188 KB Output is correct
26 Correct 1588 ms 17684 KB Output is correct
27 Correct 1777 ms 17628 KB Output is correct
28 Correct 1316 ms 20140 KB Output is correct
29 Correct 1547 ms 16256 KB Output is correct
30 Correct 1338 ms 18292 KB Output is correct
31 Correct 1451 ms 18216 KB Output is correct
32 Correct 1465 ms 18104 KB Output is correct
33 Correct 1364 ms 17080 KB Output is correct
34 Correct 1475 ms 17204 KB Output is correct
35 Correct 1534 ms 17740 KB Output is correct
36 Correct 1087 ms 16220 KB Output is correct
37 Correct 1271 ms 18212 KB Output is correct
38 Correct 1471 ms 16312 KB Output is correct
39 Correct 1445 ms 17300 KB Output is correct
40 Correct 1513 ms 17108 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 2 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 344 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 2064 ms 19476 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 2 ms 340 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 344 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 719 ms 15084 KB Output is correct
12 Correct 771 ms 14684 KB Output is correct
13 Correct 820 ms 14032 KB Output is correct
14 Correct 758 ms 14024 KB Output is correct
15 Correct 648 ms 15068 KB Output is correct
16 Correct 689 ms 14288 KB Output is correct
17 Correct 871 ms 14260 KB Output is correct
18 Correct 464 ms 16028 KB Output is correct
19 Correct 867 ms 13092 KB Output is correct
20 Correct 620 ms 14792 KB Output is correct
21 Correct 1362 ms 18168 KB Output is correct
22 Correct 1443 ms 18364 KB Output is correct
23 Correct 1834 ms 17368 KB Output is correct
24 Correct 1616 ms 17144 KB Output is correct
25 Correct 1485 ms 19188 KB Output is correct
26 Correct 1588 ms 17684 KB Output is correct
27 Correct 1777 ms 17628 KB Output is correct
28 Correct 1316 ms 20140 KB Output is correct
29 Correct 1547 ms 16256 KB Output is correct
30 Correct 1338 ms 18292 KB Output is correct
31 Correct 1451 ms 18216 KB Output is correct
32 Correct 1465 ms 18104 KB Output is correct
33 Correct 1364 ms 17080 KB Output is correct
34 Correct 1475 ms 17204 KB Output is correct
35 Correct 1534 ms 17740 KB Output is correct
36 Correct 1087 ms 16220 KB Output is correct
37 Correct 1271 ms 18212 KB Output is correct
38 Correct 1471 ms 16312 KB Output is correct
39 Correct 1445 ms 17300 KB Output is correct
40 Correct 1513 ms 17108 KB Output is correct
41 Execution timed out 2064 ms 19476 KB Time limit exceeded
42 Halted 0 ms 0 KB -