oj.uz

Submission #61445

# Submission time Handle Problem Language Result Execution time Memory
61445 2018-07-26T03:44:44 Z Benq Snake Escaping (JOI18_snake_escaping) C++11
5 / 100
 395 ms 66560 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1<<20;

int L,Q, dp[2][MX];
short pc[MX], val[MX];

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> L >> Q;
    FOR(i,1,MX) pc[i] = pc[i-(i&-i)]+1;
    string S; cin >> S;
    F0R(i,1<<L) dp[1][i] = dp[0][(1<<L)-1-i] = val[i] = S[i]-'0';
    
    F0R(i,L) F0R(j,1<<L) if (j&(1<<i)) 
        F0R(k,2) dp[k][j] += dp[k][j^(1<<i)];
}

int solve(const string& T) {
    int a = 0, b = 0, c = 0;
    F0R(i,sz(T)) {
        switch(T[sz(T)-1-i]) {
            case '0':
                a ^= 1<<i;
                break;
            case '1':
                b ^= 1<<i;
                break;
            default:
                c ^= 1<<i;
                break;
        }
    }
    
    int ans = 0;
    int mn = min(min(pc[a],pc[b]),pc[c]);
    if (pc[a] == mn) {
        for (int m = a; ; m = (m-1)&a) {
            if ((pc[a]-pc[m])&1) ans -= dp[0][m|c];
            else ans += dp[0][m|c];
            if (m == 0) break;
        }
    } else if (pc[b] == mn) {
        for (int m = b; ; m = (m-1)&b) {
            if ((pc[b]-pc[m])&1) ans -= dp[1][m|c];
            else ans += dp[1][m|c];
            if (m == 0) break;
        }
    } else {
        for (int m = c; ; m = (m-1)&c) {
            ans += val[m|b];
            if (m == 0) break;
        }
    }
    
    return ans;
}

int main() {
    init();
    F0R(i,Q) {
        string T; cin >> T;
        cout << solve(T) << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 8 ms 2544 KB Output is correct
3 Correct 6 ms 2616 KB Output is correct
4 Correct 7 ms 2616 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 7 ms 2636 KB Output is correct
7 Correct 5 ms 2636 KB Output is correct
8 Correct 6 ms 2636 KB Output is correct
9 Correct 7 ms 2800 KB Output is correct
10 Correct 6 ms 2800 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 8 ms 2544 KB Output is correct
3 Correct 6 ms 2616 KB Output is correct
4 Correct 7 ms 2616 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 7 ms 2636 KB Output is correct
7 Correct 5 ms 2636 KB Output is correct
8 Correct 6 ms 2636 KB Output is correct
9 Correct 7 ms 2800 KB Output is correct
10 Correct 6 ms 2800 KB Output is correct
11 Correct 320 ms 17524 KB Output is correct
12 Correct 346 ms 24016 KB Output is correct
13 Correct 352 ms 24016 KB Output is correct
14 Correct 350 ms 24016 KB Output is correct
15 Correct 287 ms 24252 KB Output is correct
16 Correct 395 ms 24252 KB Output is correct
17 Correct 355 ms 34492 KB Output is correct
18 Correct 385 ms 46796 KB Output is correct
19 Correct 348 ms 54652 KB Output is correct
20 Runtime error 304 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 8 ms 2544 KB Output is correct
3 Correct 6 ms 2616 KB Output is correct
4 Correct 7 ms 2616 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 7 ms 2636 KB Output is correct
7 Correct 5 ms 2636 KB Output is correct
8 Correct 6 ms 2636 KB Output is correct
9 Correct 7 ms 2800 KB Output is correct
10 Correct 6 ms 2800 KB Output is correct
11 Correct 320 ms 17524 KB Output is correct
12 Correct 346 ms 24016 KB Output is correct
13 Correct 352 ms 24016 KB Output is correct
14 Correct 350 ms 24016 KB Output is correct
15 Correct 287 ms 24252 KB Output is correct
16 Correct 395 ms 24252 KB Output is correct
17 Correct 355 ms 34492 KB Output is correct
18 Correct 385 ms 46796 KB Output is correct
19 Correct 348 ms 54652 KB Output is correct
20 Runtime error 304 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 8 ms 2544 KB Output is correct
3 Correct 6 ms 2616 KB Output is correct
4 Correct 7 ms 2616 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 7 ms 2636 KB Output is correct
7 Correct 5 ms 2636 KB Output is correct
8 Correct 6 ms 2636 KB Output is correct
9 Correct 7 ms 2800 KB Output is correct
10 Correct 6 ms 2800 KB Output is correct
11 Runtime error 95 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 8 ms 2544 KB Output is correct
3 Correct 6 ms 2616 KB Output is correct
4 Correct 7 ms 2616 KB Output is correct
5 Correct 7 ms 2624 KB Output is correct
6 Correct 7 ms 2636 KB Output is correct
7 Correct 5 ms 2636 KB Output is correct
8 Correct 6 ms 2636 KB Output is correct
9 Correct 7 ms 2800 KB Output is correct
10 Correct 6 ms 2800 KB Output is correct
11 Correct 320 ms 17524 KB Output is correct
12 Correct 346 ms 24016 KB Output is correct
13 Correct 352 ms 24016 KB Output is correct
14 Correct 350 ms 24016 KB Output is correct
15 Correct 287 ms 24252 KB Output is correct
16 Correct 395 ms 24252 KB Output is correct
17 Correct 355 ms 34492 KB Output is correct
18 Correct 385 ms 46796 KB Output is correct
19 Correct 348 ms 54652 KB Output is correct
20 Runtime error 304 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.