oj.uz

Submission #399855

# Submission time Handle Problem Language Result Execution time Memory
399855 2021-05-06T18:15:43 Z MarcoMeijer Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 33124 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<<20);
const int SQ = 8;

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;
}


int bm;
int getTot(int x) {
    if(tot[x] != -1) return tot[x];
    if(nxt2[x] == -1) {
        return tot[x] = a[bm|nxt1[x]];
    } else {
        return tot[x] = getTot(nxt1[x]) + getTot(nxt2[x]);
    }
}

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)) {
        bm = (i<<(20-SQ));
        memset(tot,-1,sizeof(tot));
        int ri = ~i;
        RE(j,q)
            if((query0[j]&i) == 0 && (query1[j]&ri) == 0)
                ans[j] += getTot(lst[j]);
    }

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8568 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 136 ms 8628 KB Output is correct
4 Correct 138 ms 8644 KB Output is correct
5 Correct 137 ms 8632 KB Output is correct
6 Correct 140 ms 8644 KB Output is correct
7 Correct 138 ms 8592 KB Output is correct
8 Correct 139 ms 8644 KB Output is correct
9 Correct 136 ms 8516 KB Output is correct
10 Correct 139 ms 8628 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8568 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 136 ms 8628 KB Output is correct
4 Correct 138 ms 8644 KB Output is correct
5 Correct 137 ms 8632 KB Output is correct
6 Correct 140 ms 8644 KB Output is correct
7 Correct 138 ms 8592 KB Output is correct
8 Correct 139 ms 8644 KB Output is correct
9 Correct 136 ms 8516 KB Output is correct
10 Correct 139 ms 8628 KB Output is correct
11 Correct 785 ms 24368 KB Output is correct
12 Correct 746 ms 23936 KB Output is correct
13 Correct 762 ms 23216 KB Output is correct
14 Correct 769 ms 23272 KB Output is correct
15 Correct 755 ms 24348 KB Output is correct
16 Correct 819 ms 23420 KB Output is correct
17 Correct 797 ms 23464 KB Output is correct
18 Correct 739 ms 25412 KB Output is correct
19 Correct 779 ms 22352 KB Output is correct
20 Correct 799 ms 23932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8568 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 136 ms 8628 KB Output is correct
4 Correct 138 ms 8644 KB Output is correct
5 Correct 137 ms 8632 KB Output is correct
6 Correct 140 ms 8644 KB Output is correct
7 Correct 138 ms 8592 KB Output is correct
8 Correct 139 ms 8644 KB Output is correct
9 Correct 136 ms 8516 KB Output is correct
10 Correct 139 ms 8628 KB Output is correct
11 Correct 785 ms 24368 KB Output is correct
12 Correct 746 ms 23936 KB Output is correct
13 Correct 762 ms 23216 KB Output is correct
14 Correct 769 ms 23272 KB Output is correct
15 Correct 755 ms 24348 KB Output is correct
16 Correct 819 ms 23420 KB Output is correct
17 Correct 797 ms 23464 KB Output is correct
18 Correct 739 ms 25412 KB Output is correct
19 Correct 779 ms 22352 KB Output is correct
20 Correct 799 ms 23932 KB Output is correct
21 Correct 809 ms 28236 KB Output is correct
22 Correct 766 ms 24552 KB Output is correct
23 Correct 797 ms 27504 KB Output is correct
24 Correct 798 ms 27332 KB Output is correct
25 Correct 781 ms 29252 KB Output is correct
26 Correct 837 ms 27844 KB Output is correct
27 Correct 862 ms 27816 KB Output is correct
28 Correct 766 ms 26380 KB Output is correct
29 Correct 799 ms 26232 KB Output is correct
30 Correct 818 ms 28388 KB Output is correct
31 Correct 816 ms 28384 KB Output is correct
32 Correct 805 ms 28268 KB Output is correct
33 Correct 803 ms 27100 KB Output is correct
34 Correct 827 ms 27332 KB Output is correct
35 Correct 860 ms 27764 KB Output is correct
36 Correct 735 ms 26364 KB Output is correct
37 Correct 756 ms 24324 KB Output is correct
38 Correct 802 ms 26388 KB Output is correct
39 Correct 819 ms 27580 KB Output is correct
40 Correct 806 ms 27332 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8568 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 136 ms 8628 KB Output is correct
4 Correct 138 ms 8644 KB Output is correct
5 Correct 137 ms 8632 KB Output is correct
6 Correct 140 ms 8644 KB Output is correct
7 Correct 138 ms 8592 KB Output is correct
8 Correct 139 ms 8644 KB Output is correct
9 Correct 136 ms 8516 KB Output is correct
10 Correct 139 ms 8628 KB Output is correct
11 Correct 274 ms 14608 KB Output is correct
12 Correct 363 ms 14696 KB Output is correct
13 Correct 261 ms 14820 KB Output is correct
14 Correct 377 ms 14772 KB Output is correct
15 Correct 1161 ms 14960 KB Output is correct
16 Correct 478 ms 14820 KB Output is correct
17 Correct 486 ms 14900 KB Output is correct
18 Correct 233 ms 14564 KB Output is correct
19 Correct 200 ms 14668 KB Output is correct
20 Correct 350 ms 14688 KB Output is correct
21 Correct 778 ms 14796 KB Output is correct
22 Correct 378 ms 14820 KB Output is correct
23 Correct 252 ms 14868 KB Output is correct
24 Correct 323 ms 14860 KB Output is correct
25 Correct 475 ms 14820 KB Output is correct
26 Correct 169 ms 14564 KB Output is correct
27 Correct 266 ms 14708 KB Output is correct
28 Correct 194 ms 14756 KB Output is correct
29 Correct 296 ms 14812 KB Output is correct
30 Correct 332 ms 14792 KB Output is correct
31 Correct 201 ms 14716 KB Output is correct
32 Correct 483 ms 14808 KB Output is correct
33 Correct 481 ms 14792 KB Output is correct
34 Correct 175 ms 14564 KB Output is correct
35 Correct 554 ms 14820 KB Output is correct
36 Correct 547 ms 14828 KB Output is correct
37 Correct 557 ms 14820 KB Output is correct
38 Correct 537 ms 14820 KB Output is correct
39 Correct 564 ms 14796 KB Output is correct
40 Correct 562 ms 14916 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8568 KB Output is correct
2 Correct 137 ms 8608 KB Output is correct
3 Correct 136 ms 8628 KB Output is correct
4 Correct 138 ms 8644 KB Output is correct
5 Correct 137 ms 8632 KB Output is correct
6 Correct 140 ms 8644 KB Output is correct
7 Correct 138 ms 8592 KB Output is correct
8 Correct 139 ms 8644 KB Output is correct
9 Correct 136 ms 8516 KB Output is correct
10 Correct 139 ms 8628 KB Output is correct
11 Correct 785 ms 24368 KB Output is correct
12 Correct 746 ms 23936 KB Output is correct
13 Correct 762 ms 23216 KB Output is correct
14 Correct 769 ms 23272 KB Output is correct
15 Correct 755 ms 24348 KB Output is correct
16 Correct 819 ms 23420 KB Output is correct
17 Correct 797 ms 23464 KB Output is correct
18 Correct 739 ms 25412 KB Output is correct
19 Correct 779 ms 22352 KB Output is correct
20 Correct 799 ms 23932 KB Output is correct
21 Correct 809 ms 28236 KB Output is correct
22 Correct 766 ms 24552 KB Output is correct
23 Correct 797 ms 27504 KB Output is correct
24 Correct 798 ms 27332 KB Output is correct
25 Correct 781 ms 29252 KB Output is correct
26 Correct 837 ms 27844 KB Output is correct
27 Correct 862 ms 27816 KB Output is correct
28 Correct 766 ms 26380 KB Output is correct
29 Correct 799 ms 26232 KB Output is correct
30 Correct 818 ms 28388 KB Output is correct
31 Correct 816 ms 28384 KB Output is correct
32 Correct 805 ms 28268 KB Output is correct
33 Correct 803 ms 27100 KB Output is correct
34 Correct 827 ms 27332 KB Output is correct
35 Correct 860 ms 27764 KB Output is correct
36 Correct 735 ms 26364 KB Output is correct
37 Correct 756 ms 24324 KB Output is correct
38 Correct 802 ms 26388 KB Output is correct
39 Correct 819 ms 27580 KB Output is correct
40 Correct 806 ms 27332 KB Output is correct
41 Correct 274 ms 14608 KB Output is correct
42 Correct 363 ms 14696 KB Output is correct
43 Correct 261 ms 14820 KB Output is correct
44 Correct 377 ms 14772 KB Output is correct
45 Correct 1161 ms 14960 KB Output is correct
46 Correct 478 ms 14820 KB Output is correct
47 Correct 486 ms 14900 KB Output is correct
48 Correct 233 ms 14564 KB Output is correct
49 Correct 200 ms 14668 KB Output is correct
50 Correct 350 ms 14688 KB Output is correct
51 Correct 778 ms 14796 KB Output is correct
52 Correct 378 ms 14820 KB Output is correct
53 Correct 252 ms 14868 KB Output is correct
54 Correct 323 ms 14860 KB Output is correct
55 Correct 475 ms 14820 KB Output is correct
56 Correct 169 ms 14564 KB Output is correct
57 Correct 266 ms 14708 KB Output is correct
58 Correct 194 ms 14756 KB Output is correct
59 Correct 296 ms 14812 KB Output is correct
60 Correct 332 ms 14792 KB Output is correct
61 Correct 201 ms 14716 KB Output is correct
62 Correct 483 ms 14808 KB Output is correct
63 Correct 481 ms 14792 KB Output is correct
64 Correct 175 ms 14564 KB Output is correct
65 Correct 554 ms 14820 KB Output is correct
66 Correct 547 ms 14828 KB Output is correct
67 Correct 557 ms 14820 KB Output is correct
68 Correct 537 ms 14820 KB Output is correct
69 Correct 564 ms 14796 KB Output is correct
70 Correct 562 ms 14916 KB Output is correct
71 Correct 1415 ms 30644 KB Output is correct
72 Correct 1551 ms 30728 KB Output is correct
73 Correct 1991 ms 33124 KB Output is correct
74 Execution timed out 2097 ms 29452 KB Time limit exceeded
75 Halted 0 ms 0 KB -