oj.uz

Submission #619727

# Submission time Handle Problem Language Result Execution time Memory
619727 2022-08-02T15:15:55 Z Do_you_copy Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 19484 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;
}

int A[21], B[21], C[21];

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;
    }
    int x, y, z;
    while (q--){
        cin >> t;
        x = y = z = 0;
        vector <int> val((1 << n) + 1, 0);
        for (int i = 0; i < int(t.length()); ++i){
            if (t[i] == '0') A[x++] = n - i - 1;
            if (t[i] == '1') B[y++] = n - i - 1;
            if (t[i] == '?') C[z++] = n - i - 1;
        }
        if (x <= n / 3){
            int tem = 0, ans = 0;
            for (int i = 0; i < z; ++i) tem += 1 << C[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 <= n / 3){
            int tem = 0, ans = 0;
            for (int i = 0; i < z; ++i) tem += 1 << C[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 (int i = 0; i < y; ++i) tem += 1 << B[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:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         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 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 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 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 295 ms 8660 KB Output is correct
12 Correct 297 ms 8356 KB Output is correct
13 Correct 316 ms 7524 KB Output is correct
14 Correct 328 ms 7644 KB Output is correct
15 Correct 297 ms 8668 KB Output is correct
16 Correct 323 ms 7884 KB Output is correct
17 Correct 335 ms 7788 KB Output is correct
18 Correct 258 ms 9624 KB Output is correct
19 Correct 287 ms 6588 KB Output is correct
20 Correct 308 ms 8340 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 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 295 ms 8660 KB Output is correct
12 Correct 297 ms 8356 KB Output is correct
13 Correct 316 ms 7524 KB Output is correct
14 Correct 328 ms 7644 KB Output is correct
15 Correct 297 ms 8668 KB Output is correct
16 Correct 323 ms 7884 KB Output is correct
17 Correct 335 ms 7788 KB Output is correct
18 Correct 258 ms 9624 KB Output is correct
19 Correct 287 ms 6588 KB Output is correct
20 Correct 308 ms 8340 KB Output is correct
21 Correct 1014 ms 8876 KB Output is correct
22 Correct 991 ms 8896 KB Output is correct
23 Correct 1068 ms 8076 KB Output is correct
24 Correct 1036 ms 7808 KB Output is correct
25 Correct 992 ms 9892 KB Output is correct
26 Correct 1053 ms 8276 KB Output is correct
27 Correct 1029 ms 8264 KB Output is correct
28 Correct 929 ms 11008 KB Output is correct
29 Correct 958 ms 6852 KB Output is correct
30 Correct 960 ms 9052 KB Output is correct
31 Correct 1154 ms 8948 KB Output is correct
32 Correct 1158 ms 8764 KB Output is correct
33 Correct 1087 ms 7720 KB Output is correct
34 Correct 1252 ms 7832 KB Output is correct
35 Correct 1037 ms 8224 KB Output is correct
36 Correct 901 ms 6496 KB Output is correct
37 Correct 993 ms 8344 KB Output is correct
38 Correct 960 ms 6224 KB Output is correct
39 Correct 1006 ms 7376 KB Output is correct
40 Correct 1061 ms 7244 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 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Execution timed out 2047 ms 19484 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 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 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 295 ms 8660 KB Output is correct
12 Correct 297 ms 8356 KB Output is correct
13 Correct 316 ms 7524 KB Output is correct
14 Correct 328 ms 7644 KB Output is correct
15 Correct 297 ms 8668 KB Output is correct
16 Correct 323 ms 7884 KB Output is correct
17 Correct 335 ms 7788 KB Output is correct
18 Correct 258 ms 9624 KB Output is correct
19 Correct 287 ms 6588 KB Output is correct
20 Correct 308 ms 8340 KB Output is correct
21 Correct 1014 ms 8876 KB Output is correct
22 Correct 991 ms 8896 KB Output is correct
23 Correct 1068 ms 8076 KB Output is correct
24 Correct 1036 ms 7808 KB Output is correct
25 Correct 992 ms 9892 KB Output is correct
26 Correct 1053 ms 8276 KB Output is correct
27 Correct 1029 ms 8264 KB Output is correct
28 Correct 929 ms 11008 KB Output is correct
29 Correct 958 ms 6852 KB Output is correct
30 Correct 960 ms 9052 KB Output is correct
31 Correct 1154 ms 8948 KB Output is correct
32 Correct 1158 ms 8764 KB Output is correct
33 Correct 1087 ms 7720 KB Output is correct
34 Correct 1252 ms 7832 KB Output is correct
35 Correct 1037 ms 8224 KB Output is correct
36 Correct 901 ms 6496 KB Output is correct
37 Correct 993 ms 8344 KB Output is correct
38 Correct 960 ms 6224 KB Output is correct
39 Correct 1006 ms 7376 KB Output is correct
40 Correct 1061 ms 7244 KB Output is correct
41 Execution timed out 2047 ms 19484 KB Time limit exceeded
42 Halted 0 ms 0 KB -