Submission #963539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963539	2024-04-15T09:38:12 Z	ksu2009en	Snake Escaping (JOI18_snake_escaping)	C++17	Compilation error	0 ms	0 KB

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(max(half, l - half) + 2);
    pw[0] = 1;
    
    for(int i = 1; i < pw.size(); i++)
        pw[i] = pw[i - 1] * 3;
        
    vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
    
    for(int i = 0; i < (1 << max(0, l - half)); i++){
        ll cnt = 0;
        
        for(int j = max(0, 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(0, l - half))]; i++){
        ll val = i;
        
        for(int j = 0; j < max(0, 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(0, 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

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:47:42: error: no matching function for call to 'max(int, ll)'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                          ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:42: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                          ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:42: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                          ^
snake_escaping.cpp:47:86: error: no matching function for call to 'max(int, ll)'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:86: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:86: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:86: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:86: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                      ^
snake_escaping.cpp:47:126: error: no matching function for call to 'max(int, ll)'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                                                              ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:126: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                                                              ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:126: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:126: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:47:126: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   47 |     vector<ll> dp, bit(pw[max(0, l - half)] + 1, -1), bin_to3((1ll << max(0, l - half)) + 1), from3_to_bin(pw[max(0, l - half)] + 1);
      |                                                                                                                              ^
snake_escaping.cpp:49:45: error: no matching function for call to 'max(int, ll)'
   49 |     for(int i = 0; i < (1 << max(0, l - half)); i++){
      |                                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:49:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   49 |     for(int i = 0; i < (1 << max(0, l - half)); i++){
      |                                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:49:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   49 |     for(int i = 0; i < (1 << max(0, l - half)); i++){
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:49:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   49 |     for(int i = 0; i < (1 << max(0, l - half)); i++){
      |                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:49:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   49 |     for(int i = 0; i < (1 << max(0, l - half)); i++){
      |                                             ^
snake_escaping.cpp:52:36: error: no matching function for call to 'max(int, ll)'
   52 |         for(int j = max(0, l - half) - 1; j >= 0; j--){
      |                                    ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:52:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   52 |         for(int j = max(0, l - half) - 1; j >= 0; j--){
      |                                    ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:52:36: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   52 |         for(int j = max(0, l - half) - 1; j >= 0; j--){
      |                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:52:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   52 |         for(int j = max(0, l - half) - 1; j >= 0; j--){
      |                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from snake_escaping.cpp:11:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:52:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   52 |         for(int j = max(0, l - half) - 1; j >= 0; j--){
      |                                    ^
snake_escaping.cpp:65:43: error: no matching function for call to 'max(int, ll)'
   65 |     for(int i = 0; i < pw[(max(0, l - half))]; i++){
      |                                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from snake_escaping.cpp:4:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
snake_escaping.cpp:65:43: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'll' {aka 'long long int'})
   65 |     for(int i = 0; i < pw[(max(0, l - half))]; i++){
      |                                           ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/