Submission #82915

#	Time	Username	Problem	Language	Result	Execution time	Memory
82915		alexpetrescu	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	294 ms	66560 KiB

snake_escaping

#include <cstdio>
#include <algorithm>

#define fin stdin
#define fout stdout
//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");

#define MAXN 20
#define MAXL (1 << MAXN)

int n, q, l, cnt[2], a[MAXN], v[MAXN];
int dp0[MAXL], dp1[MAXL];
char u[MAXL + 10], s[MAXN + 10];

inline void solve() {
    fgets(s, MAXN + 5, fin);
    for (int i = 0, j = n - 1; i < j; i++, j--)
        std::swap(s[i], s[j]);
    cnt[0] = cnt[1] = 0;
    for (int i = 0; i < n; i++)
        if (s[i] != '?')
            cnt[s[i] - '0']++;
    v[0] = 0;
    long long ans = 0;
    if (n - cnt[0] - cnt[1] <= cnt[0] && n - cnt[0] - cnt[1] <= cnt[1]) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '?')
                v[++v[0]] = i;
            else if (s[i] == '1')
                x += 1 << i;
        }
        for (int i = 1; i <= v[0]; i++)
            a[i] = 0;
        ans = u[x] - '0';
        for (int i = 1; i < (1 << v[0]); i++) {
            int p = 1;
            while (a[p]) {
                x -= 1 << v[p];
                a[p] = 0;
                p++;
            }
            x += 1 << v[p];
            a[p] = 1;
            ans += u[x] - '0';
        }
    } else if (cnt[0] <= cnt[1]) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0')
                v[++v[0]] = i;
            else if (s[i] == '1')
                x += 1 << i;
        }
        for (int i = 0; i < n; i++)
            a[i] = 0;
        ans = dp1[x];
        int S = 1;
        for (int i = 1; i < (1 << v[0]); i++) {
            int p = 1;
            while (a[p]) {
                S = -S;
                x -= 1 << v[p];
                a[p] = 0;
                p++;
            }
            S = -S;
            x += 1 << v[p];
            a[p] = 1;
            ans += S * dp1[x];
        }
    } else {
        int x = l - 1;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1')
                v[++v[0]] = i;
            else if (s[i] == '0')
                x -= 1 << i;
        }
        for (int i = 0; i < n; i++)
            a[i] = 0;
        ans = dp0[x];
        int S = 1;
        for (int i = 1; i < (1 << v[0]); i++) {
            int p = 1;
            while (a[p]) {
                S = -S;
                x += 1 << v[p];
                a[p] = 0;
                p++;
            }
            S = -S;
            x -= 1 << v[p];
            a[p] = 1;
            ans += S * dp0[x];
        }
    }
    fprintf(fout, "%lld\n", ans);
}

int main() {
    fscanf(fin, "%d%d ", &n, &q);
    fgets(u, MAXL + 5, fin);
    l = 1 << n;
    for (int i = 0; i < l; i++)
        dp0[i] = dp1[i] = u[i] - '0';

    for (int i = 0; i < n; i++)
        for (int j = 0; j < l; j++)
            if (!(j & (1 << i)))
                dp1[j] += dp1[j ^ (1 << i)];
    for (int i = 0; i < n; i++)
        for (int j = l - 1; j >= 0; j--)
            if (j & (1 << i))
                dp0[j] += dp0[j ^ (1 << i)];

    for (; q; q--)
        solve();

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:102:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d%d ", &n, &q);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:103:10: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(u, MAXL + 5, fin);
     ~~~~~^~~~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:16:10: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets(s, MAXN + 5, fin);
     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25