oj.uz

Submission #256757

# Submission time Handle Problem Language Result Execution time Memory
256757 2020-08-03T07:43:44 Z 반딧불(#5039) Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 384 KB 
#include <iostream>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

typedef long long ll;

int n, q;
char arr[1048579];
char str[100];
int DP[1048576]; /// 0�� Ȯ��, 1�� 0and1
int DP2[1048576]; /// 1�� Ȯ��, 0�� 0and1

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    cin >> arr;
    for(int i=0; i<(1<<n); i++){
        DP[i] = DP2[i] = arr[i] - '0';
    }
    for(int d=0; d<n; d++){
        for(int i=0; i<(1<<n); i++){
            if(i & (1<<d)) DP[i] += DP[i|(1<<d)];
            else DP2[i] += DP2[i^(1<<d)];
        }
    }

    for(int i=1; i<=q; i++){
        int one = 0;
        int zero = 0;
        int lft = 0;
        cin >> str;
        for(int j=n-1; j>=0; j--){
            char c = str[n-1-j];
            if(c=='1') one |= (1<<j);
            else if(c=='0') zero |= (1<<j);
            else lft |= (1<<j);
        }

        int ans = 0;
        if(__builtin_popcount(one) > __builtin_popcount(zero)){
            for(int x=zero; 1; x = (x-1)&zero){
                ans += DP2[one|x] * (__builtin_popcount(x) & 1 ? -1 : 1);
                if(!x) break;
            }
        }
        else{
            for(int x=one; 1; x = (x-1)&one){
                ans += DP[lft|x] * (__builtin_popcount(one ^ x) & 1 ? -1 : 1);
                if(!x) break;
            }
        }
        cout << ans << '\n';
    }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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