oj.uz

Submission #399851

# Submission time Handle Problem Language Result Execution time Memory
399851 2021-05-06T18:08:25 Z MarcoMeijer Snake Escaping (JOI18_snake_escaping) C++14
58 / 100
 1473 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int N = (1<<23);
const int SQ = 6;

int n, l, q;
int a[N];
int nxt1[N], nxt2[N];
int tot[N], ans[N];
string s;
int query0[N], query1[N];
int lst[N];

int stringToInt(string s) {
    int res = 0;
    RE(i,20-SQ) {
        res *= 3;
        if(s[i] == '0') res += 0;
        if(s[i] == '1') res += 1;
        if(s[i] == '?') res += 2;
    }
    return res;
}
string intToString(int x) {
    string res;
    RE(_,20-SQ) {
        if((x%3) == 0) res += '0';
        if((x%3) == 1) res += '1';
        if((x%3) == 2) res += '?';
        x /= 3;
    }
    reverse(all(res));
    return res;
}

void program() {
    // pre calculations
    int ways3 = 1;
    RE(_,20-SQ) ways3 *= 3;
    RE(i,ways3) {
        string t = intToString(i);
        nxt1[i] = -1, nxt2[i] = -1;
        RE(j,20-SQ) if(t[j] == '?') {
            t[j] = '0';
            nxt1[i] = stringToInt(t);
            t[j] = '1';
            nxt2[i] = stringToInt(t);
            break;
        }
        if(nxt1[i] == -1) {
            nxt1[i] = 0;
            RE(j,20-SQ) if(t[19-SQ-j] == '1') nxt1[i] |= (1<<j);
        }
    }

    // input
    IN(l,q,s); n=(1<<l);
    RE(i,n) a[i] = s[i]-'0';
    string u; u.assign(20-l,'0');
    RE(i,q) {
        string t; IN(t);
        t = u + t;
        RE(j,SQ) if(t[SQ-1-j] == '0') query0[i] |= (1<<j);
        RE(j,SQ) if(t[SQ-1-j] == '1') query1[i] |= (1<<j);
        lst[i] = stringToInt(t.substr(SQ,20-SQ));
    }

    RE(i,(1<<SQ)) {
        int bm = (i<<(20-SQ));
        RE(j,ways3) {
            if(nxt2[j] == -1) {
                tot[j] = a[bm|nxt1[j]];
            } else {
                tot[j] = tot[nxt1[j]] + tot[nxt2[j]];
            }
        }
        RE(j,q)
            if((query0[j]&i) == 0 && (query1[j]&(~i)) == 0)
                ans[j] += tot[lst[j]];
    }

    RE(i,q) OUTL(ans[i]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 56636 KB Output is correct
2 Correct 1384 ms 56544 KB Output is correct
3 Correct 1356 ms 56644 KB Output is correct
4 Correct 1356 ms 56704 KB Output is correct
5 Correct 1353 ms 56676 KB Output is correct
6 Correct 1357 ms 56644 KB Output is correct
7 Correct 1357 ms 56772 KB Output is correct
8 Correct 1361 ms 56644 KB Output is correct
9 Correct 1370 ms 56636 KB Output is correct
10 Correct 1388 ms 56656 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 56636 KB Output is correct
2 Correct 1384 ms 56544 KB Output is correct
3 Correct 1356 ms 56644 KB Output is correct
4 Correct 1356 ms 56704 KB Output is correct
5 Correct 1353 ms 56676 KB Output is correct
6 Correct 1357 ms 56644 KB Output is correct
7 Correct 1357 ms 56772 KB Output is correct
8 Correct 1361 ms 56644 KB Output is correct
9 Correct 1370 ms 56636 KB Output is correct
10 Correct 1388 ms 56656 KB Output is correct
11 Runtime error 1215 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 56636 KB Output is correct
2 Correct 1384 ms 56544 KB Output is correct
3 Correct 1356 ms 56644 KB Output is correct
4 Correct 1356 ms 56704 KB Output is correct
5 Correct 1353 ms 56676 KB Output is correct
6 Correct 1357 ms 56644 KB Output is correct
7 Correct 1357 ms 56772 KB Output is correct
8 Correct 1361 ms 56644 KB Output is correct
9 Correct 1370 ms 56636 KB Output is correct
10 Correct 1388 ms 56656 KB Output is correct
11 Runtime error 1215 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 56636 KB Output is correct
2 Correct 1384 ms 56544 KB Output is correct
3 Correct 1356 ms 56644 KB Output is correct
4 Correct 1356 ms 56704 KB Output is correct
5 Correct 1353 ms 56676 KB Output is correct
6 Correct 1357 ms 56644 KB Output is correct
7 Correct 1357 ms 56772 KB Output is correct
8 Correct 1361 ms 56644 KB Output is correct
9 Correct 1370 ms 56636 KB Output is correct
10 Correct 1388 ms 56656 KB Output is correct
11 Correct 1399 ms 63224 KB Output is correct
12 Correct 1393 ms 63296 KB Output is correct
13 Correct 1410 ms 63332 KB Output is correct
14 Correct 1418 ms 63332 KB Output is correct
15 Correct 1428 ms 63684 KB Output is correct
16 Correct 1413 ms 63408 KB Output is correct
17 Correct 1473 ms 63316 KB Output is correct
18 Correct 1415 ms 63284 KB Output is correct
19 Correct 1440 ms 63308 KB Output is correct
20 Correct 1418 ms 63360 KB Output is correct
21 Correct 1423 ms 63580 KB Output is correct
22 Correct 1423 ms 63636 KB Output is correct
23 Correct 1441 ms 63472 KB Output is correct
24 Correct 1401 ms 63452 KB Output is correct
25 Correct 1417 ms 63596 KB Output is correct
26 Correct 1369 ms 63164 KB Output is correct
27 Correct 1403 ms 63416 KB Output is correct
28 Correct 1397 ms 63320 KB Output is correct
29 Correct 1404 ms 63552 KB Output is correct
30 Correct 1405 ms 63468 KB Output is correct
31 Correct 1393 ms 63588 KB Output is correct
32 Correct 1416 ms 63516 KB Output is correct
33 Correct 1397 ms 63472 KB Output is correct
34 Correct 1376 ms 63104 KB Output is correct
35 Correct 1409 ms 63444 KB Output is correct
36 Correct 1408 ms 63456 KB Output is correct
37 Correct 1403 ms 63456 KB Output is correct
38 Correct 1407 ms 63616 KB Output is correct
39 Correct 1412 ms 63460 KB Output is correct
40 Correct 1422 ms 63544 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 56636 KB Output is correct
2 Correct 1384 ms 56544 KB Output is correct
3 Correct 1356 ms 56644 KB Output is correct
4 Correct 1356 ms 56704 KB Output is correct
5 Correct 1353 ms 56676 KB Output is correct
6 Correct 1357 ms 56644 KB Output is correct
7 Correct 1357 ms 56772 KB Output is correct
8 Correct 1361 ms 56644 KB Output is correct
9 Correct 1370 ms 56636 KB Output is correct
10 Correct 1388 ms 56656 KB Output is correct
11 Runtime error 1215 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -