oj.uz

Submission #399850

# Submission time Handle Problem Language Result Execution time Memory
399850 2021-05-06T18:04:22 Z MarcoMeijer Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 65536 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<<21);
const int SQ = 7;

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 570 ms 19224 KB Output is correct
2 Correct 565 ms 19092 KB Output is correct
3 Correct 574 ms 19224 KB Output is correct
4 Correct 596 ms 19236 KB Output is correct
5 Correct 566 ms 19008 KB Output is correct
6 Correct 596 ms 19112 KB Output is correct
7 Correct 615 ms 19204 KB Output is correct
8 Correct 564 ms 19120 KB Output is correct
9 Correct 583 ms 19012 KB Output is correct
10 Correct 576 ms 19220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 19224 KB Output is correct
2 Correct 565 ms 19092 KB Output is correct
3 Correct 574 ms 19224 KB Output is correct
4 Correct 596 ms 19236 KB Output is correct
5 Correct 566 ms 19008 KB Output is correct
6 Correct 596 ms 19112 KB Output is correct
7 Correct 615 ms 19204 KB Output is correct
8 Correct 564 ms 19120 KB Output is correct
9 Correct 583 ms 19012 KB Output is correct
10 Correct 576 ms 19220 KB Output is correct
11 Correct 1028 ms 35336 KB Output is correct
12 Correct 981 ms 35064 KB Output is correct
13 Correct 993 ms 34372 KB Output is correct
14 Correct 994 ms 35308 KB Output is correct
15 Correct 997 ms 36244 KB Output is correct
16 Correct 1016 ms 35380 KB Output is correct
17 Correct 1006 ms 35336 KB Output is correct
18 Correct 984 ms 37272 KB Output is correct
19 Correct 1029 ms 34236 KB Output is correct
20 Correct 1028 ms 35996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 19224 KB Output is correct
2 Correct 565 ms 19092 KB Output is correct
3 Correct 574 ms 19224 KB Output is correct
4 Correct 596 ms 19236 KB Output is correct
5 Correct 566 ms 19008 KB Output is correct
6 Correct 596 ms 19112 KB Output is correct
7 Correct 615 ms 19204 KB Output is correct
8 Correct 564 ms 19120 KB Output is correct
9 Correct 583 ms 19012 KB Output is correct
10 Correct 576 ms 19220 KB Output is correct
11 Correct 1028 ms 35336 KB Output is correct
12 Correct 981 ms 35064 KB Output is correct
13 Correct 993 ms 34372 KB Output is correct
14 Correct 994 ms 35308 KB Output is correct
15 Correct 997 ms 36244 KB Output is correct
16 Correct 1016 ms 35380 KB Output is correct
17 Correct 1006 ms 35336 KB Output is correct
18 Correct 984 ms 37272 KB Output is correct
19 Correct 1029 ms 34236 KB Output is correct
20 Correct 1028 ms 35996 KB Output is correct
21 Correct 1030 ms 36296 KB Output is correct
22 Correct 987 ms 36444 KB Output is correct
23 Correct 1016 ms 35548 KB Output is correct
24 Correct 1016 ms 35296 KB Output is correct
25 Correct 1010 ms 37196 KB Output is correct
26 Correct 1036 ms 35636 KB Output is correct
27 Correct 1040 ms 35600 KB Output is correct
28 Correct 992 ms 38084 KB Output is correct
29 Correct 1018 ms 33840 KB Output is correct
30 Correct 1042 ms 36064 KB Output is correct
31 Correct 1008 ms 35944 KB Output is correct
32 Correct 1032 ms 35872 KB Output is correct
33 Correct 1024 ms 34828 KB Output is correct
34 Correct 1026 ms 34648 KB Output is correct
35 Correct 1045 ms 35168 KB Output is correct
36 Correct 980 ms 33756 KB Output is correct
37 Correct 986 ms 35704 KB Output is correct
38 Correct 1048 ms 33732 KB Output is correct
39 Correct 1034 ms 34896 KB Output is correct
40 Correct 1024 ms 34724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 19224 KB Output is correct
2 Correct 565 ms 19092 KB Output is correct
3 Correct 574 ms 19224 KB Output is correct
4 Correct 596 ms 19236 KB Output is correct
5 Correct 566 ms 19008 KB Output is correct
6 Correct 596 ms 19112 KB Output is correct
7 Correct 615 ms 19204 KB Output is correct
8 Correct 564 ms 19120 KB Output is correct
9 Correct 583 ms 19012 KB Output is correct
10 Correct 576 ms 19220 KB Output is correct
11 Correct 614 ms 25232 KB Output is correct
12 Correct 605 ms 25368 KB Output is correct
13 Correct 615 ms 25444 KB Output is correct
14 Correct 621 ms 25404 KB Output is correct
15 Correct 644 ms 25636 KB Output is correct
16 Correct 620 ms 25404 KB Output is correct
17 Correct 621 ms 25404 KB Output is correct
18 Correct 585 ms 25416 KB Output is correct
19 Correct 605 ms 25372 KB Output is correct
20 Correct 608 ms 25316 KB Output is correct
21 Correct 632 ms 25512 KB Output is correct
22 Correct 639 ms 25484 KB Output is correct
23 Correct 626 ms 25472 KB Output is correct
24 Correct 625 ms 25404 KB Output is correct
25 Correct 621 ms 25440 KB Output is correct
26 Correct 597 ms 25252 KB Output is correct
27 Correct 601 ms 25316 KB Output is correct
28 Correct 629 ms 25312 KB Output is correct
29 Correct 625 ms 25444 KB Output is correct
30 Correct 627 ms 25516 KB Output is correct
31 Correct 602 ms 25444 KB Output is correct
32 Correct 626 ms 25408 KB Output is correct
33 Correct 635 ms 25472 KB Output is correct
34 Correct 590 ms 25176 KB Output is correct
35 Correct 637 ms 25532 KB Output is correct
36 Correct 630 ms 25444 KB Output is correct
37 Correct 630 ms 25444 KB Output is correct
38 Correct 623 ms 25440 KB Output is correct
39 Correct 632 ms 25456 KB Output is correct
40 Correct 643 ms 25448 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 19224 KB Output is correct
2 Correct 565 ms 19092 KB Output is correct
3 Correct 574 ms 19224 KB Output is correct
4 Correct 596 ms 19236 KB Output is correct
5 Correct 566 ms 19008 KB Output is correct
6 Correct 596 ms 19112 KB Output is correct
7 Correct 615 ms 19204 KB Output is correct
8 Correct 564 ms 19120 KB Output is correct
9 Correct 583 ms 19012 KB Output is correct
10 Correct 576 ms 19220 KB Output is correct
11 Correct 1028 ms 35336 KB Output is correct
12 Correct 981 ms 35064 KB Output is correct
13 Correct 993 ms 34372 KB Output is correct
14 Correct 994 ms 35308 KB Output is correct
15 Correct 997 ms 36244 KB Output is correct
16 Correct 1016 ms 35380 KB Output is correct
17 Correct 1006 ms 35336 KB Output is correct
18 Correct 984 ms 37272 KB Output is correct
19 Correct 1029 ms 34236 KB Output is correct
20 Correct 1028 ms 35996 KB Output is correct
21 Correct 1030 ms 36296 KB Output is correct
22 Correct 987 ms 36444 KB Output is correct
23 Correct 1016 ms 35548 KB Output is correct
24 Correct 1016 ms 35296 KB Output is correct
25 Correct 1010 ms 37196 KB Output is correct
26 Correct 1036 ms 35636 KB Output is correct
27 Correct 1040 ms 35600 KB Output is correct
28 Correct 992 ms 38084 KB Output is correct
29 Correct 1018 ms 33840 KB Output is correct
30 Correct 1042 ms 36064 KB Output is correct
31 Correct 1008 ms 35944 KB Output is correct
32 Correct 1032 ms 35872 KB Output is correct
33 Correct 1024 ms 34828 KB Output is correct
34 Correct 1026 ms 34648 KB Output is correct
35 Correct 1045 ms 35168 KB Output is correct
36 Correct 980 ms 33756 KB Output is correct
37 Correct 986 ms 35704 KB Output is correct
38 Correct 1048 ms 33732 KB Output is correct
39 Correct 1034 ms 34896 KB Output is correct
40 Correct 1024 ms 34724 KB Output is correct
41 Correct 614 ms 25232 KB Output is correct
42 Correct 605 ms 25368 KB Output is correct
43 Correct 615 ms 25444 KB Output is correct
44 Correct 621 ms 25404 KB Output is correct
45 Correct 644 ms 25636 KB Output is correct
46 Correct 620 ms 25404 KB Output is correct
47 Correct 621 ms 25404 KB Output is correct
48 Correct 585 ms 25416 KB Output is correct
49 Correct 605 ms 25372 KB Output is correct
50 Correct 608 ms 25316 KB Output is correct
51 Correct 632 ms 25512 KB Output is correct
52 Correct 639 ms 25484 KB Output is correct
53 Correct 626 ms 25472 KB Output is correct
54 Correct 625 ms 25404 KB Output is correct
55 Correct 621 ms 25440 KB Output is correct
56 Correct 597 ms 25252 KB Output is correct
57 Correct 601 ms 25316 KB Output is correct
58 Correct 629 ms 25312 KB Output is correct
59 Correct 625 ms 25444 KB Output is correct
60 Correct 627 ms 25516 KB Output is correct
61 Correct 602 ms 25444 KB Output is correct
62 Correct 626 ms 25408 KB Output is correct
63 Correct 635 ms 25472 KB Output is correct
64 Correct 590 ms 25176 KB Output is correct
65 Correct 637 ms 25532 KB Output is correct
66 Correct 630 ms 25444 KB Output is correct
67 Correct 630 ms 25444 KB Output is correct
68 Correct 623 ms 25440 KB Output is correct
69 Correct 632 ms 25456 KB Output is correct
70 Correct 643 ms 25448 KB Output is correct
71 Correct 1300 ms 41096 KB Output is correct
72 Correct 1287 ms 41188 KB Output is correct
73 Correct 1478 ms 43636 KB Output is correct
74 Correct 1739 ms 44036 KB Output is correct
75 Correct 1996 ms 45948 KB Output is correct
76 Correct 1883 ms 65536 KB Output is correct
77 Correct 1886 ms 65536 KB Output is correct
78 Correct 1045 ms 61764 KB Output is correct
79 Correct 1392 ms 63504 KB Output is correct
80 Correct 1345 ms 62924 KB Output is correct
81 Execution timed out 2029 ms 65536 KB Time limit exceeded
82 Halted 0 ms 0 KB -