oj.uz

Submission #966947

# Submission time Handle Problem Language Result Execution time Memory
966947 2024-04-20T16:53:57 Z efedmrlr Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 20044 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,q;
vector<int> dp, dpr;
int RVSR;
inline void solve() {
    cin>>n>>q;
    dp.assign((1 << n), 0);
    dpr.assign((1 << n), 0);
    RVSR = (1 << n) - 1;
    for(int i = 0; i < (1 << n); i++) {
        char tmp;
        cin >> tmp;
        dp[i] = dpr[i ^ RVSR] = tmp - '0';
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < (1 << n); i++) {
            if(i & (1 << k)) {
                dp[i] += dp[i ^ (1 << k)];
                dpr[i] += dpr[i ^ (1 << k)];
            }
        }
    }
    // for(int i = 0; i < (1 << n); i++) {
    //     cout << "i:" << i <<" dp:" << dp[i] << " dpr:" << dpr[i] << "\n";
    // }
    REP(z, q) {
        string s;
        cin >> s;
        reverse(all(s));
        int cnt0 = 0, cnt1 = 0;
        for(char c : s) {
            if(c == '0') cnt0++;
            else if(c == '1') cnt1++;
        }
        int ans = 0;
        if(cnt1 > cnt0) {   // use reverse
            int x = 0;
            vector<int> occ;
            for(int i = 0; i < n; i++) {
                if(s[i] != '1') x += (1 << i);
                if(s[i] == '0') {
                    occ.pb(i);
                }
            }
            for(int mask = 0; mask < (1 << ((int)occ.size())); mask++) {
                int cur = x;
                for(int i = 0; i < occ.size(); i++) {
                    if(mask & (1 << i)) {
                        cur ^= 1 << (occ[i]);
                    }
                }
                if(__popcount(mask) & 1) {
                    ans -= dpr[cur];
                }
                else {
                    ans += dpr[cur];
                }
            }
        }
        else {
            int x = 0;
            vector<int> occ;
            for(int i = 0; i < n; i++) {
                if(s[i] != '0') x += (1 << i);
                if(s[i] == '1') {
                    occ.pb(i);
                }
            }
            for(int mask = 0; mask < (1 << ((int)occ.size())); mask++) {
                int cur = x;
                // cout << "mask:" << mask << " cur:" << cur << "\n";
                for(int i = 0; i < occ.size(); i++) {
                    if(mask & (1 << i)) {
                        cur ^= 1 << (occ[i]);
                    }
                }
                if(__popcount(mask) & 1) {
                    ans -= dp[cur];
                }
                else {
                    ans += dp[cur];
                }
            }
        }
        cout << ans << endl;
    }

   

}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:74:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 for(int i = 0; i < occ.size(); i++) {
      |                                ~~^~~~~~~~~~~~
snake_escaping.cpp:99:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 for(int i = 0; i < occ.size(); i++) {
      |                                ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1332 ms 15428 KB Output is correct
12 Correct 1325 ms 15064 KB Output is correct
13 Correct 1443 ms 13980 KB Output is correct
14 Correct 1466 ms 14124 KB Output is correct
15 Correct 1350 ms 14952 KB Output is correct
16 Correct 1428 ms 14344 KB Output is correct
17 Correct 1454 ms 14528 KB Output is correct
18 Correct 1211 ms 16392 KB Output is correct
19 Correct 1659 ms 12956 KB Output is correct
20 Correct 1314 ms 14852 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1332 ms 15428 KB Output is correct
12 Correct 1325 ms 15064 KB Output is correct
13 Correct 1443 ms 13980 KB Output is correct
14 Correct 1466 ms 14124 KB Output is correct
15 Correct 1350 ms 14952 KB Output is correct
16 Correct 1428 ms 14344 KB Output is correct
17 Correct 1454 ms 14528 KB Output is correct
18 Correct 1211 ms 16392 KB Output is correct
19 Correct 1659 ms 12956 KB Output is correct
20 Correct 1314 ms 14852 KB Output is correct
21 Correct 1279 ms 18260 KB Output is correct
22 Correct 1362 ms 18484 KB Output is correct
23 Correct 1661 ms 17396 KB Output is correct
24 Correct 1576 ms 17088 KB Output is correct
25 Correct 1438 ms 19352 KB Output is correct
26 Correct 1582 ms 17860 KB Output is correct
27 Correct 1568 ms 17492 KB Output is correct
28 Correct 1250 ms 20044 KB Output is correct
29 Execution timed out 2049 ms 15032 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 105 ms 11092 KB Output is correct
12 Correct 105 ms 10932 KB Output is correct
13 Correct 166 ms 10764 KB Output is correct
14 Correct 150 ms 10704 KB Output is correct
15 Correct 108 ms 10936 KB Output is correct
16 Correct 142 ms 10832 KB Output is correct
17 Correct 163 ms 10836 KB Output is correct
18 Correct 96 ms 11092 KB Output is correct
19 Execution timed out 2041 ms 10964 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 1332 ms 15428 KB Output is correct
12 Correct 1325 ms 15064 KB Output is correct
13 Correct 1443 ms 13980 KB Output is correct
14 Correct 1466 ms 14124 KB Output is correct
15 Correct 1350 ms 14952 KB Output is correct
16 Correct 1428 ms 14344 KB Output is correct
17 Correct 1454 ms 14528 KB Output is correct
18 Correct 1211 ms 16392 KB Output is correct
19 Correct 1659 ms 12956 KB Output is correct
20 Correct 1314 ms 14852 KB Output is correct
21 Correct 1279 ms 18260 KB Output is correct
22 Correct 1362 ms 18484 KB Output is correct
23 Correct 1661 ms 17396 KB Output is correct
24 Correct 1576 ms 17088 KB Output is correct
25 Correct 1438 ms 19352 KB Output is correct
26 Correct 1582 ms 17860 KB Output is correct
27 Correct 1568 ms 17492 KB Output is correct
28 Correct 1250 ms 20044 KB Output is correct
29 Execution timed out 2049 ms 15032 KB Time limit exceeded
30 Halted 0 ms 0 KB -