oj.uz

Submission #619783

# Submission time Handle Problem Language Result Execution time Memory
619783 2022-08-02T15:48:27 Z Do_you_copy Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 19312 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;
    }
    int x, y, z;
    int mask1, mask0, tem;
    while (q--){
        cin >> t;
        x = y = z = mask1 = mask0 = tem = 0;
        vector <int> val((1 << n) + 1, 0);
        reverse(t.begin(), t.end());
        for (int i = 0; i < n; ++i){
            if (t[i] == '0') ++x, mask0 ^= 1 << i;
            if (t[i] == '1') ++y, mask1 ^= 1 << i;
            if (t[i] == '?') ++z, tem ^= 1 << i;
        }
        if (z <= n / 3){
            //brute all ?s
            int ans = s[mask1] - '0';
            for (int i = tem; i; i = (i - 1) & tem){
                ans += s[i + mask1] - '0';
            }
            WriteInt(ans);
            putchar('\n');
        }
        else if (x <= n / 3){
            int ans = -f[tem];
            for (int i = mask0; i; i = (i - 1) & mask0){
                if (cnt[i] & 1) ans += f[i + tem];
                else ans -= f[i + tem];
            }
            ans = abs(ans);
            WriteInt(ans);
            putchar('\n');
        }
        else{
            int ans = -dp[tem];
            for (int i = mask1; i; i = (i - 1) & mask1){
                if (cnt[i] & 1) ans += dp[i + tem];
                else ans -= dp[i + tem];
            }
            ans = abs(ans);
            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:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         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 326 ms 12288 KB Output is correct
12 Correct 316 ms 11852 KB Output is correct
13 Correct 365 ms 11256 KB Output is correct
14 Correct 317 ms 11248 KB Output is correct
15 Correct 329 ms 12208 KB Output is correct
16 Correct 350 ms 11388 KB Output is correct
17 Correct 354 ms 11348 KB Output is correct
18 Correct 330 ms 13244 KB Output is correct
19 Correct 305 ms 10316 KB Output is correct
20 Correct 352 ms 11872 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 326 ms 12288 KB Output is correct
12 Correct 316 ms 11852 KB Output is correct
13 Correct 365 ms 11256 KB Output is correct
14 Correct 317 ms 11248 KB Output is correct
15 Correct 329 ms 12208 KB Output is correct
16 Correct 350 ms 11388 KB Output is correct
17 Correct 354 ms 11348 KB Output is correct
18 Correct 330 ms 13244 KB Output is correct
19 Correct 305 ms 10316 KB Output is correct
20 Correct 352 ms 11872 KB Output is correct
21 Correct 1030 ms 12324 KB Output is correct
22 Correct 1176 ms 12384 KB Output is correct
23 Correct 1139 ms 11420 KB Output is correct
24 Correct 1081 ms 11204 KB Output is correct
25 Correct 1116 ms 13304 KB Output is correct
26 Correct 1278 ms 11744 KB Output is correct
27 Correct 1094 ms 11680 KB Output is correct
28 Correct 994 ms 14292 KB Output is correct
29 Correct 1016 ms 10360 KB Output is correct
30 Correct 1087 ms 12584 KB Output is correct
31 Correct 1050 ms 12252 KB Output is correct
32 Correct 1114 ms 12288 KB Output is correct
33 Correct 1032 ms 11124 KB Output is correct
34 Correct 1107 ms 11396 KB Output is correct
35 Correct 1092 ms 11676 KB Output is correct
36 Correct 992 ms 10428 KB Output is correct
37 Correct 1086 ms 12128 KB Output is correct
38 Correct 1002 ms 9916 KB Output is correct
39 Correct 1051 ms 10824 KB Output is correct
40 Correct 1054 ms 10412 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 2075 ms 19312 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 326 ms 12288 KB Output is correct
12 Correct 316 ms 11852 KB Output is correct
13 Correct 365 ms 11256 KB Output is correct
14 Correct 317 ms 11248 KB Output is correct
15 Correct 329 ms 12208 KB Output is correct
16 Correct 350 ms 11388 KB Output is correct
17 Correct 354 ms 11348 KB Output is correct
18 Correct 330 ms 13244 KB Output is correct
19 Correct 305 ms 10316 KB Output is correct
20 Correct 352 ms 11872 KB Output is correct
21 Correct 1030 ms 12324 KB Output is correct
22 Correct 1176 ms 12384 KB Output is correct
23 Correct 1139 ms 11420 KB Output is correct
24 Correct 1081 ms 11204 KB Output is correct
25 Correct 1116 ms 13304 KB Output is correct
26 Correct 1278 ms 11744 KB Output is correct
27 Correct 1094 ms 11680 KB Output is correct
28 Correct 994 ms 14292 KB Output is correct
29 Correct 1016 ms 10360 KB Output is correct
30 Correct 1087 ms 12584 KB Output is correct
31 Correct 1050 ms 12252 KB Output is correct
32 Correct 1114 ms 12288 KB Output is correct
33 Correct 1032 ms 11124 KB Output is correct
34 Correct 1107 ms 11396 KB Output is correct
35 Correct 1092 ms 11676 KB Output is correct
36 Correct 992 ms 10428 KB Output is correct
37 Correct 1086 ms 12128 KB Output is correct
38 Correct 1002 ms 9916 KB Output is correct
39 Correct 1051 ms 10824 KB Output is correct
40 Correct 1054 ms 10412 KB Output is correct
41 Execution timed out 2075 ms 19312 KB Time limit exceeded
42 Halted 0 ms 0 KB -