Submission #963542

#	Time	Username	Problem	Language	Result	Execution time	Memory
963542		ksu2009en	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1277 ms	65536 KiB

snake_escaping

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2")

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>


using namespace std;
typedef long long ll;

ll const half = 7;

#define endl '\n'

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll l, q;
    cin >> l >> q;
    
    string a;
    cin >> a;
    
    vector<ll> pw(l + 1);
    pw[0] = 1;
    
    for(int i = 1; i < pw.size(); i++)
        pw[i] = pw[i - 1] * 3;
        
    vector<int> dp, bit(pw[max(0ll, l - half)] + 1, -1), bin_to3((1ll << max(0ll, l - half)) + 1), from3_to_bin(pw[max(0ll, l - half)] + 1);
    
    for(int i = 0; i < (1 << max(0ll, l - half)); i++){
        ll cnt = 0;
        
        for(int j = max(0ll, l - half) - 1; j >= 0; j--){
            if((i >> j) & 1){
                cnt = (cnt + 1) * 3;
            }
            else
                cnt *= 3;
        }
        cnt /= 3;
        bin_to3[i] = cnt;
        from3_to_bin[cnt] = i;
        
    }
    
    for(int i = 0; i < pw[(max(0ll, l - half))]; i++){
        ll val = i;
        
        for(int j = 0; j < max(0ll, l - half); j++){
            if(val % 3 == 2){
                bit[i] = j;
                break;
            }
            
            val /= 3;
        }
    }
    
    vector<vector<bool>> sub(pw[half], vector<bool> ((1ll << half) + 1, true));
    
    for(int i = 0; i < pw[half]; i++){
        vector<ll> u;
        
        ll cur = pw[half];
        
        ll val = i;
        for(int i = half - 1; i >= 0; i--){
            cur /= 3;
            u.push_back(val / cur);
            val %= cur;
        }
        
        for(int j = 0; j < (1ll << half); j++){
            for(int k = 0; k < half; k++){
                if(u[u.size() - k - 1] == 2)
                    continue;
                
                if(u[u.size() - k - 1] != (j >> k) % 2){
                    sub[i][j] = false;
                    break;
                }
            }
        }
    }
    
    vector<pair<ll, ll>> quer;
    
    while(q--){
        string b;
        cin >> b;
        
        while(b.size() < l)
            b += "0";
        
        ll cnt = 0, pos = 0, c1 = 0;
        
        for(auto i: b){
            if(i == '0'){
                cnt *= 3;
            }
            else if(i == '1'){
                cnt = (cnt + 1) * 3;
            }
            else{
                cnt = (cnt + 2) * 3;
            }
            pos++;
            
            if(pos == half || (half > b.size() && pos == b.size()) ){
                c1 = cnt / 3;
            }
        }
        
        cnt /= 3;
        if(l > half){
            cnt %= pw[l - half];
        }
                
        quer.push_back({c1, cnt});
    }
        
    vector<ll> ans(quer.size());
    
    
    dp.resize(pw[max(0ll, l - half)] + 1);
    for(int i = 0; i < (1ll << min(half, l)); i++){
        if(l <= half){
            for(int j = 0; j < quer.size(); j++){
                if(sub[quer[j].first][i])
                    ans[j] += (a[i] - '0');
            }
            continue;
        }
        
        ll add = i * (1 << (l - half));
        for(int j = 0; j < pw[l - half]; j++){
            if(bit[j] == -1){
//                cout << j << ' ' << from3_to_bin[j] << ' ' << add << endl;
                dp[j] = (a[add + from3_to_bin[j]] - '0');
                continue;
            }
            
            dp[j] = 0;
            ll c1 = j - 2 * pw[bit[j]];
            dp[j] += dp[c1];
            
            c1 = j - pw[bit[j]];
            dp[j] += dp[c1];
        }
//
//        cout << i << endl;
//        for(int j = 0; j < pw[l - half]; j++)
//            cout << dp[j] << ' ';
//        cout << endl;
//
        for(int j = 0; j < quer.size(); j++){
            if(sub[quer[j].first][i]){
                
                ans[j] += dp[quer[j].second];
            }
        }
    }
    
    for(auto i: ans)
        cout << i << endl;
    
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 1; i < pw.size(); i++)
      |                    ~~^~~~~~~~~~~
snake_escaping.cpp:111:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  111 |         while(b.size() < l)
      |               ~~~~~~~~~^~~
snake_escaping.cpp:128:55: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             if(pos == half || (half > b.size() && pos == b.size()) ){
      |                                                   ~~~~^~~~~~~~~~~
snake_escaping.cpp:147:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             for(int j = 0; j < quer.size(); j++){
      |                            ~~^~~~~~~~~~~~~
snake_escaping.cpp:175:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         for(int j = 0; j < quer.size(); j++){
      |                        ~~^~~~~~~~~~~~~

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