oj.uz

Submission #1039300

# Submission time Handle Problem Language Result Execution time Memory
1039300 2024-07-30T16:39:20 Z phong Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 16156 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 4e5 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 31, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int L, q;
string s;
int F[1 << 20], G[1 << 20], cnt[1 << 20];
int bit(int msk, int x){
    return msk>> x & 1;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> L >> q;
    cin >> s;

    for(int i = 0; i < (1 << L) ; ++i){
        int c1 = 0, c2 = 0;
        for(int k = 1; k <= L; ++k){
            if(bit(i, L - k)){
                c1 += (1 << (k - 1));
            }
            else c2 += (1 << (k - 1));
        }
        cnt[c1] += s[i] - '0';
        F[c1] += s[i] - '0';
        G[c2] += s[i] - '0';
    }
    for(int i = 0; i < L; ++i){
        for(int msk = 0; msk < (1 << L); ++msk){
            if(!bit(msk, i)){
                F[msk ^ (1 << i)] += F[msk];
                G[msk ^ (1 << i)] += G[msk];
            }
        }
    }
    string tmp;
    vector<int> c0, c1, c2;
    while(q--){
        cin >> tmp;
        c0.clear(); c1.clear();c2.clear();
        for(int i = 0; i < L; ++i){
            char x = tmp[i];
            if(x == '0'){
                c0.push_back(i);
            }
            else if(x == '1'){
                c1.push_back(i);
            }
            else c2.push_back(i);
        }
        if((int)c1.size() <= -2){
//                cout << "%";
            int res = 0;
            for(auto p : c1) res += (1 << p);
            for(auto p : c2) res += (1 << p);
            ll ans = 0;
            for(int msk = 0; msk < (1 << c1.size()); ++msk){
                int cur = res;
                for(int i = 0; i < c1.size(); ++i){
                    if(bit(msk, i)){
                        cur ^= (1 << c1[i]);
                    }
                }
                int s = __builtin_popcount(msk);
                if(s & 1) ans -= F[cur];
                else ans += F[cur];
            }
            cout << ans << endl;
        }
        else if((int)c0.size() <= -2){
//                cout << "?";
            int res = 0;
            for(auto p : c0) res += (1 << p);
            for(auto p : c2) res += (1 << p);
            ll ans = 0;
            for(int msk = 0; msk < (1 << c0.size()); ++msk){
                int cur = res;
                for(int i = 0; i < c0.size(); ++i){
                    if(bit(msk, i)){
                        cur ^= (1 << c0[i]);
                    }
                }
                int s = __builtin_popcount(msk);
                if(s & 1) ans -= G[cur];
                else ans += G[cur];
            }
            cout << ans << endl;
        }
        else{
//            cout << "#";
            int res = 0;
            for(auto p : c1) res += (1 << p);
            int ans = 0;
            for(int msk = 0; msk < (1 << c2.size()); ++msk){
                int cur = res;
                for(int i = 0; i < c2.size(); ++i){
                    if(bit(msk, i)){
                        cur ^= (1 << c2[i]);
                    }
                }
                ans += cnt[cur];
            }
            cout << ans << endl;
        }
    }
}
/*
3 5
12345678
000
0??
1?0
?11
???

3 1
12345678
???
*/

Compilation message

snake_escaping.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for(int i = 0; i < c1.size(); ++i){
      |                                ~~^~~~~~~~~~~
snake_escaping.cpp:94:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for(int i = 0; i < c0.size(); ++i){
      |                                ~~^~~~~~~~~~~
snake_escaping.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for(int i = 0; i < c2.size(); ++i){
      |                                ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 289 ms 15188 KB Output is correct
12 Correct 579 ms 14672 KB Output is correct
13 Correct 191 ms 13908 KB Output is correct
14 Correct 186 ms 14224 KB Output is correct
15 Correct 469 ms 15472 KB Output is correct
16 Correct 249 ms 14160 KB Output is correct
17 Correct 286 ms 14152 KB Output is correct
18 Execution timed out 2047 ms 4128 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 289 ms 15188 KB Output is correct
12 Correct 579 ms 14672 KB Output is correct
13 Correct 191 ms 13908 KB Output is correct
14 Correct 186 ms 14224 KB Output is correct
15 Correct 469 ms 15472 KB Output is correct
16 Correct 249 ms 14160 KB Output is correct
17 Correct 286 ms 14152 KB Output is correct
18 Execution timed out 2047 ms 4128 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 571 ms 16156 KB Output is correct
12 Execution timed out 2099 ms 15492 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 10 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 289 ms 15188 KB Output is correct
12 Correct 579 ms 14672 KB Output is correct
13 Correct 191 ms 13908 KB Output is correct
14 Correct 186 ms 14224 KB Output is correct
15 Correct 469 ms 15472 KB Output is correct
16 Correct 249 ms 14160 KB Output is correct
17 Correct 286 ms 14152 KB Output is correct
18 Execution timed out 2047 ms 4128 KB Time limit exceeded
19 Halted 0 ms 0 KB -