oj.uz

Submission #82912

# Submission time Handle Problem Language Result Execution time Memory
82912 2018-11-02T20:16:39 Z alexpetrescu Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 2 ms 664 KB 
#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 u[MAXL], dp0[MAXL], dp1[MAXL];
char s[MAXL + 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];
        for (int i = 1; i < (1 << v[0]); i++) {
            int p = 1;
            while (a[p]) {
                x -= 1 << v[i];
                a[p] = 0;
                p++;
            }
            x += 1 << v[p];
            a[p] = 1;
            ans += u[x];
        }
    } 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[i];
                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[i];
                a[p] = 0;
                p++;
            }
            S = -S;
            x -= 1 << v[p];
            a[p] = 1;
            ans += S * dp0[x];
        }
    }
    fprintf(fout, "%I64d\n", ans);
}

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

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:98:33: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
     fprintf(fout, "%I64d\n", ans);
                                 ^
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(s, 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Incorrect 2 ms 664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Incorrect 2 ms 664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Incorrect 2 ms 664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Incorrect 2 ms 664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Incorrect 2 ms 664 KB Output isn't correct
4 Halted 0 ms 0 KB -