oj.uz

Submission #966955

# Submission time Handle Problem Language Result Execution time Memory
966955 2024-04-20T17:31:36 Z efedmrlr Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 25204 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:38: 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:38: 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 3 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 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 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 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 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1261 ms 4220 KB Output is correct
12 Correct 1324 ms 4180 KB Output is correct
13 Correct 1435 ms 3168 KB Output is correct
14 Correct 1463 ms 3648 KB Output is correct
15 Correct 1413 ms 4572 KB Output is correct
16 Correct 1442 ms 3668 KB Output is correct
17 Correct 1481 ms 3856 KB Output is correct
18 Correct 1212 ms 5444 KB Output is correct
19 Correct 1653 ms 2344 KB Output is correct
20 Correct 1303 ms 4092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 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 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1261 ms 4220 KB Output is correct
12 Correct 1324 ms 4180 KB Output is correct
13 Correct 1435 ms 3168 KB Output is correct
14 Correct 1463 ms 3648 KB Output is correct
15 Correct 1413 ms 4572 KB Output is correct
16 Correct 1442 ms 3668 KB Output is correct
17 Correct 1481 ms 3856 KB Output is correct
18 Correct 1212 ms 5444 KB Output is correct
19 Correct 1653 ms 2344 KB Output is correct
20 Correct 1303 ms 4092 KB Output is correct
21 Correct 1267 ms 4536 KB Output is correct
22 Correct 1373 ms 4540 KB Output is correct
23 Correct 1665 ms 3844 KB Output is correct
24 Correct 1549 ms 3632 KB Output is correct
25 Correct 1387 ms 5600 KB Output is correct
26 Correct 1556 ms 4052 KB Output is correct
27 Correct 1567 ms 3876 KB Output is correct
28 Correct 1225 ms 6472 KB Output is correct
29 Correct 1994 ms 2408 KB Output is correct
30 Correct 1284 ms 11752 KB Output is correct
31 Correct 1501 ms 11516 KB Output is correct
32 Correct 1551 ms 11704 KB Output is correct
33 Correct 1481 ms 10668 KB Output is correct
34 Correct 1559 ms 10632 KB Output is correct
35 Correct 1543 ms 11220 KB Output is correct
36 Correct 1219 ms 9732 KB Output is correct
37 Correct 1388 ms 11452 KB Output is correct
38 Correct 1870 ms 9508 KB Output is correct
39 Correct 1629 ms 10872 KB Output is correct
40 Correct 1531 ms 10792 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 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 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 109 ms 8676 KB Output is correct
12 Correct 109 ms 8788 KB Output is correct
13 Correct 160 ms 10072 KB Output is correct
14 Correct 141 ms 10064 KB Output is correct
15 Correct 110 ms 10064 KB Output is correct
16 Correct 141 ms 10072 KB Output is correct
17 Correct 159 ms 10028 KB Output is correct
18 Correct 100 ms 10324 KB Output is correct
19 Correct 1974 ms 9984 KB Output is correct
20 Correct 113 ms 10136 KB Output is correct
21 Correct 122 ms 10172 KB Output is correct
22 Correct 144 ms 10064 KB Output is correct
23 Correct 138 ms 10268 KB Output is correct
24 Correct 153 ms 9940 KB Output is correct
25 Correct 160 ms 10064 KB Output is correct
26 Correct 97 ms 9992 KB Output is correct
27 Correct 110 ms 10068 KB Output is correct
28 Correct 1022 ms 10092 KB Output is correct
29 Correct 162 ms 10068 KB Output is correct
30 Correct 182 ms 9944 KB Output is correct
31 Correct 118 ms 10072 KB Output is correct
32 Correct 148 ms 9920 KB Output is correct
33 Correct 166 ms 9936 KB Output is correct
34 Correct 97 ms 9816 KB Output is correct
35 Correct 274 ms 10064 KB Output is correct
36 Correct 280 ms 10564 KB Output is correct
37 Correct 274 ms 10224 KB Output is correct
38 Correct 280 ms 10340 KB Output is correct
39 Correct 300 ms 9936 KB Output is correct
40 Correct 270 ms 9936 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 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 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 1261 ms 4220 KB Output is correct
12 Correct 1324 ms 4180 KB Output is correct
13 Correct 1435 ms 3168 KB Output is correct
14 Correct 1463 ms 3648 KB Output is correct
15 Correct 1413 ms 4572 KB Output is correct
16 Correct 1442 ms 3668 KB Output is correct
17 Correct 1481 ms 3856 KB Output is correct
18 Correct 1212 ms 5444 KB Output is correct
19 Correct 1653 ms 2344 KB Output is correct
20 Correct 1303 ms 4092 KB Output is correct
21 Correct 1267 ms 4536 KB Output is correct
22 Correct 1373 ms 4540 KB Output is correct
23 Correct 1665 ms 3844 KB Output is correct
24 Correct 1549 ms 3632 KB Output is correct
25 Correct 1387 ms 5600 KB Output is correct
26 Correct 1556 ms 4052 KB Output is correct
27 Correct 1567 ms 3876 KB Output is correct
28 Correct 1225 ms 6472 KB Output is correct
29 Correct 1994 ms 2408 KB Output is correct
30 Correct 1284 ms 11752 KB Output is correct
31 Correct 1501 ms 11516 KB Output is correct
32 Correct 1551 ms 11704 KB Output is correct
33 Correct 1481 ms 10668 KB Output is correct
34 Correct 1559 ms 10632 KB Output is correct
35 Correct 1543 ms 11220 KB Output is correct
36 Correct 1219 ms 9732 KB Output is correct
37 Correct 1388 ms 11452 KB Output is correct
38 Correct 1870 ms 9508 KB Output is correct
39 Correct 1629 ms 10872 KB Output is correct
40 Correct 1531 ms 10792 KB Output is correct
41 Correct 109 ms 8676 KB Output is correct
42 Correct 109 ms 8788 KB Output is correct
43 Correct 160 ms 10072 KB Output is correct
44 Correct 141 ms 10064 KB Output is correct
45 Correct 110 ms 10064 KB Output is correct
46 Correct 141 ms 10072 KB Output is correct
47 Correct 159 ms 10028 KB Output is correct
48 Correct 100 ms 10324 KB Output is correct
49 Correct 1974 ms 9984 KB Output is correct
50 Correct 113 ms 10136 KB Output is correct
51 Correct 122 ms 10172 KB Output is correct
52 Correct 144 ms 10064 KB Output is correct
53 Correct 138 ms 10268 KB Output is correct
54 Correct 153 ms 9940 KB Output is correct
55 Correct 160 ms 10064 KB Output is correct
56 Correct 97 ms 9992 KB Output is correct
57 Correct 110 ms 10068 KB Output is correct
58 Correct 1022 ms 10092 KB Output is correct
59 Correct 162 ms 10068 KB Output is correct
60 Correct 182 ms 9944 KB Output is correct
61 Correct 118 ms 10072 KB Output is correct
62 Correct 148 ms 9920 KB Output is correct
63 Correct 166 ms 9936 KB Output is correct
64 Correct 97 ms 9816 KB Output is correct
65 Correct 274 ms 10064 KB Output is correct
66 Correct 280 ms 10564 KB Output is correct
67 Correct 274 ms 10224 KB Output is correct
68 Correct 280 ms 10340 KB Output is correct
69 Correct 300 ms 9936 KB Output is correct
70 Correct 270 ms 9936 KB Output is correct
71 Correct 1456 ms 24608 KB Output is correct
72 Correct 1547 ms 25204 KB Output is correct
73 Execution timed out 2032 ms 20692 KB Time limit exceeded
74 Halted 0 ms 0 KB -