oj.uz

Submission #966948

# Submission time Handle Problem Language Result Execution time Memory
966948 2024-04-20T16:56:20 Z efedmrlr Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 35548 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 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 1240 ms 4436 KB Output is correct
12 Correct 1275 ms 3988 KB Output is correct
13 Correct 1425 ms 3256 KB Output is correct
14 Correct 1414 ms 3456 KB Output is correct
15 Correct 1336 ms 4252 KB Output is correct
16 Correct 1420 ms 3812 KB Output is correct
17 Correct 1423 ms 3412 KB Output is correct
18 Correct 1213 ms 5368 KB Output is correct
19 Correct 1609 ms 2340 KB Output is correct
20 Correct 1251 ms 3936 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 1240 ms 4436 KB Output is correct
12 Correct 1275 ms 3988 KB Output is correct
13 Correct 1425 ms 3256 KB Output is correct
14 Correct 1414 ms 3456 KB Output is correct
15 Correct 1336 ms 4252 KB Output is correct
16 Correct 1420 ms 3812 KB Output is correct
17 Correct 1423 ms 3412 KB Output is correct
18 Correct 1213 ms 5368 KB Output is correct
19 Correct 1609 ms 2340 KB Output is correct
20 Correct 1251 ms 3936 KB Output is correct
21 Correct 1284 ms 4716 KB Output is correct
22 Correct 1341 ms 4640 KB Output is correct
23 Correct 1589 ms 3816 KB Output is correct
24 Correct 1549 ms 3488 KB Output is correct
25 Correct 1376 ms 5780 KB Output is correct
26 Correct 1523 ms 3904 KB Output is correct
27 Correct 1534 ms 4000 KB Output is correct
28 Correct 1237 ms 6356 KB Output is correct
29 Correct 1977 ms 3216 KB Output is correct
30 Correct 1306 ms 18164 KB Output is correct
31 Correct 1453 ms 18100 KB Output is correct
32 Correct 1560 ms 18252 KB Output is correct
33 Correct 1467 ms 17212 KB Output is correct
34 Correct 1532 ms 17044 KB Output is correct
35 Correct 1536 ms 17688 KB Output is correct
36 Correct 1225 ms 16172 KB Output is correct
37 Correct 1328 ms 18224 KB Output is correct
38 Correct 1809 ms 16188 KB Output is correct
39 Correct 1552 ms 17232 KB Output is correct
40 Correct 1518 ms 17052 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 109 ms 8696 KB Output is correct
12 Correct 111 ms 8684 KB Output is correct
13 Correct 158 ms 8804 KB Output is correct
14 Correct 146 ms 8988 KB Output is correct
15 Correct 110 ms 8784 KB Output is correct
16 Correct 139 ms 8788 KB Output is correct
17 Correct 159 ms 8788 KB Output is correct
18 Correct 106 ms 9052 KB Output is correct
19 Correct 1960 ms 8964 KB Output is correct
20 Correct 103 ms 10876 KB Output is correct
21 Correct 118 ms 10832 KB Output is correct
22 Correct 141 ms 10864 KB Output is correct
23 Correct 122 ms 10832 KB Output is correct
24 Correct 146 ms 11092 KB Output is correct
25 Correct 161 ms 10832 KB Output is correct
26 Correct 98 ms 10580 KB Output is correct
27 Correct 112 ms 10840 KB Output is correct
28 Correct 1004 ms 10984 KB Output is correct
29 Correct 156 ms 10836 KB Output is correct
30 Correct 181 ms 10832 KB Output is correct
31 Correct 119 ms 10696 KB Output is correct
32 Correct 140 ms 10836 KB Output is correct
33 Correct 158 ms 10832 KB Output is correct
34 Correct 98 ms 10584 KB Output is correct
35 Correct 269 ms 10908 KB Output is correct
36 Correct 266 ms 10860 KB Output is correct
37 Correct 277 ms 11180 KB Output is correct
38 Correct 273 ms 10836 KB Output is correct
39 Correct 267 ms 10836 KB Output is correct
40 Correct 267 ms 10708 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 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 1240 ms 4436 KB Output is correct
12 Correct 1275 ms 3988 KB Output is correct
13 Correct 1425 ms 3256 KB Output is correct
14 Correct 1414 ms 3456 KB Output is correct
15 Correct 1336 ms 4252 KB Output is correct
16 Correct 1420 ms 3812 KB Output is correct
17 Correct 1423 ms 3412 KB Output is correct
18 Correct 1213 ms 5368 KB Output is correct
19 Correct 1609 ms 2340 KB Output is correct
20 Correct 1251 ms 3936 KB Output is correct
21 Correct 1284 ms 4716 KB Output is correct
22 Correct 1341 ms 4640 KB Output is correct
23 Correct 1589 ms 3816 KB Output is correct
24 Correct 1549 ms 3488 KB Output is correct
25 Correct 1376 ms 5780 KB Output is correct
26 Correct 1523 ms 3904 KB Output is correct
27 Correct 1534 ms 4000 KB Output is correct
28 Correct 1237 ms 6356 KB Output is correct
29 Correct 1977 ms 3216 KB Output is correct
30 Correct 1306 ms 18164 KB Output is correct
31 Correct 1453 ms 18100 KB Output is correct
32 Correct 1560 ms 18252 KB Output is correct
33 Correct 1467 ms 17212 KB Output is correct
34 Correct 1532 ms 17044 KB Output is correct
35 Correct 1536 ms 17688 KB Output is correct
36 Correct 1225 ms 16172 KB Output is correct
37 Correct 1328 ms 18224 KB Output is correct
38 Correct 1809 ms 16188 KB Output is correct
39 Correct 1552 ms 17232 KB Output is correct
40 Correct 1518 ms 17052 KB Output is correct
41 Correct 109 ms 8696 KB Output is correct
42 Correct 111 ms 8684 KB Output is correct
43 Correct 158 ms 8804 KB Output is correct
44 Correct 146 ms 8988 KB Output is correct
45 Correct 110 ms 8784 KB Output is correct
46 Correct 139 ms 8788 KB Output is correct
47 Correct 159 ms 8788 KB Output is correct
48 Correct 106 ms 9052 KB Output is correct
49 Correct 1960 ms 8964 KB Output is correct
50 Correct 103 ms 10876 KB Output is correct
51 Correct 118 ms 10832 KB Output is correct
52 Correct 141 ms 10864 KB Output is correct
53 Correct 122 ms 10832 KB Output is correct
54 Correct 146 ms 11092 KB Output is correct
55 Correct 161 ms 10832 KB Output is correct
56 Correct 98 ms 10580 KB Output is correct
57 Correct 112 ms 10840 KB Output is correct
58 Correct 1004 ms 10984 KB Output is correct
59 Correct 156 ms 10836 KB Output is correct
60 Correct 181 ms 10832 KB Output is correct
61 Correct 119 ms 10696 KB Output is correct
62 Correct 140 ms 10836 KB Output is correct
63 Correct 158 ms 10832 KB Output is correct
64 Correct 98 ms 10584 KB Output is correct
65 Correct 269 ms 10908 KB Output is correct
66 Correct 266 ms 10860 KB Output is correct
67 Correct 277 ms 11180 KB Output is correct
68 Correct 273 ms 10836 KB Output is correct
69 Correct 267 ms 10836 KB Output is correct
70 Correct 267 ms 10708 KB Output is correct
71 Correct 1443 ms 35108 KB Output is correct
72 Correct 1517 ms 35548 KB Output is correct
73 Execution timed out 2019 ms 29404 KB Time limit exceeded
74 Halted 0 ms 0 KB -