Submission #1073880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073880		Requiem	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	4696 KiB

snake_escaping

#include<bits/stdc++.h>
#define int long long
#define TASKNAME "snake"
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define se second
#define pb push_back
#define MASK(i) (1LL << i) //2^i
#define BIT(x, i) (((x) >> (i))&1) //lay bit thu i cua i

using namespace std;
typedef pair<int, int> ii;
/**
Cho n = 2^L - 1 va q truy van:
Voi truy van thu i. Ta duoc 1 chuoi str gom ?, 0, 1:
1 mask goi la khop neu khi ta so tung vi tri thi str[i] bang '?' hoac mask[i] == str[i].

subtask 1: L <= 10, n <= 1000.
subtask 2: L <= 13.
subtask 3: L <= 15
subtask 4: Q <= 50000
subtask 5: L <= 20, Q <= 1000000

Gọi X là số dấu ?
Nếu X <= 10 thì ta bruteforce.
Nếu X > 10 thì ta sẽ có tối đa 9 số. Thì ta sẽ dùng bao hàm bù trừ kết hợp dp SOS để tính nhanh.

Rõ ràng là với những dấu ? thì chúng khá là vô dụng tức là những thằng nào
Giả sử ta biết vị trí của những số 1 hay ? thì ta co cach nao lam tot hon khong.
**/

const int MAX = MASK(20);
int dp1[MAX], dp2[MAX], val[MAX];
char query[21];
int lengthBit;
int numQuery;
namespace subtask5{
    bool check(){
        return true;
    }
    vector<int> hidden;
    vector<int> number1, number0;
    int ans = 0, mask1 = 0, mask2 = 0, mask3 = 0;

    void calc1(int pos){
        if (pos == hidden.size()){
            ans += val[mask1];
            return;
        }

        calc1(pos + 1);

        mask1 ^= (1LL << hidden[pos]);
        calc1(pos + 1);
        mask1 ^= (1LL << hidden[pos]);
    }

    void calc2(int pos, int val){
        if (pos == number1.size()){
            ans += dp1[mask2] * ((val&1) ? (-1) : (1));
            return;
        }
        calc2(pos + 1, val + 1);

        mask2 ^= (1LL << number1[pos]);
        calc2(pos + 1, val);
        mask2 ^= (1LL << number1[pos]);
    }

    void calc3(int pos, int val){
        if (pos == number0.size()){
            ans += dp2[mask3] * ((val&1) ? (-1) : (1));
            return;
        }
        calc3(pos + 1, val);
        mask3 ^= (1LL << number0[pos]);
        calc3(pos + 1, val + 1);
        mask3 ^= (1LL << number0[pos]);
    }
    void solve(){
        FOR(i, 0, numQuery - 1){
            mask1 = 0, mask2 = 0, mask3 = 0, ans = 0;
            FORD(j, lengthBit - 1, 0){
                cin >> query[j];
                if (query[j] == '?') hidden.pb(j), mask2 ^= (1LL << j);
                else if (query[j] == '1') number1.pb(j), mask1 ^= (1 << j), mask2 ^= (1 << j), mask3 ^= (1 << j);
                else number0.pb(j);

            }
            if (hidden.size() <= lengthBit / 2){
                calc1(0);
                printf("%lld\n", ans);
            }
            else if (number1.size() <= 6) {
                calc2(0, 0);
                printf("%lld\n", ans);
            }
            else if (number0.size() <= 6){
                calc3(0, 0);
                printf("%lld\n", ans);
            }
            number1.clear();
            number0.clear();
            hidden.clear();
        }
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> lengthBit >> numQuery;
    FOR(i, 0, MASK(lengthBit) - 1){
        char c;
        cin >> c;
        val[i] = (c - '0');
        dp1[i] += (c - '0');
        dp2[i] += (c - '0');

    }

    FOR(j, 0, lengthBit - 1){
        FOR(i, 0, MASK(lengthBit) - 1){
            if (i & (1 << j)) dp1[i] += dp1[i ^ (1 << j)];
        }
    }
    FOR(j, 0, lengthBit - 1){
        FORD(i, MASK(lengthBit) - 1, 0){
            if (!BIT(i, j)) dp2[i] += dp2[i ^ (1 << j)];
        }
    }

//    FOR(i, 0, MASK(lengthBit) - 1) printf("%lld\n", dp[i]);

    if (subtask5::check()) return subtask5::solve(), 0;

}

Compilation message (stderr)

snake_escaping.cpp: In function 'void subtask5::calc1(long long int)':
snake_escaping.cpp:48:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (pos == hidden.size()){
      |             ~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask5::calc2(long long int, long long int)':
snake_escaping.cpp:61:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (pos == number1.size()){
      |             ~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask5::calc3(long long int, long long int)':
snake_escaping.cpp:73:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if (pos == number0.size()){
      |             ~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask5::solve()':
snake_escaping.cpp:92:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   92 |             if (hidden.size() <= lengthBit / 2){
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp: At global scope:
snake_escaping.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  110 | main(){
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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