oj.uz

Submission #399867

# Submission time Handle Problem Language Result Execution time Memory
399867 2021-05-06T18:33:25 Z MarcoMeijer Snake Escaping (JOI18_snake_escaping) C++14
65 / 100
 2000 ms 22816 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 = 9;

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 f[N], m;
int lst[N];

int stringToInt(string s) {
    int res = 0;
    RE(i,20-SQ) {
        res *= 3;
        if(s[i] == '0') res += 0;
        else if(s[i] == '1') res += 1;
        else 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;
    m = (1<<(20-SQ));
    RE(_,20-SQ) ways3 *= 3;
    int x=0, y=m;
    RE(i,ways3) {
        string t = intToString(i);
        int a = 0;
        bool hasQ = false;
        RE(j,20-SQ) if(t[j] == '?') hasQ = true;
        if(hasQ) a = y++;
        else     a = x++;
        f[i] = a;
        
        nxt1[a] = -1, nxt2[a] = -1;
        RE(j,20-SQ) if(t[j] == '?') {
            t[j] = '0';
            nxt1[a] = f[stringToInt(t)];
            t[j] = '1';
            nxt2[a] = f[stringToInt(t)];
            break;
        }
        if(!hasQ) {
            nxt1[a] = 0;
            RE(j,20-SQ) if(t[19-SQ-j] == '1') nxt1[a] |= (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] = f[stringToInt(t.substr(SQ,20-SQ))];
    }

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3168 KB Output is correct
2 Correct 142 ms 3172 KB Output is correct
3 Correct 150 ms 3176 KB Output is correct
4 Correct 143 ms 3172 KB Output is correct
5 Correct 135 ms 3180 KB Output is correct
6 Correct 145 ms 3168 KB Output is correct
7 Correct 170 ms 3140 KB Output is correct
8 Correct 150 ms 3172 KB Output is correct
9 Correct 133 ms 3172 KB Output is correct
10 Correct 138 ms 3168 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3168 KB Output is correct
2 Correct 142 ms 3172 KB Output is correct
3 Correct 150 ms 3176 KB Output is correct
4 Correct 143 ms 3172 KB Output is correct
5 Correct 135 ms 3180 KB Output is correct
6 Correct 145 ms 3168 KB Output is correct
7 Correct 170 ms 3140 KB Output is correct
8 Correct 150 ms 3172 KB Output is correct
9 Correct 133 ms 3172 KB Output is correct
10 Correct 138 ms 3168 KB Output is correct
11 Correct 1519 ms 18848 KB Output is correct
12 Correct 1483 ms 18568 KB Output is correct
13 Correct 1646 ms 17772 KB Output is correct
14 Correct 1614 ms 17888 KB Output is correct
15 Correct 1524 ms 18828 KB Output is correct
16 Correct 1605 ms 17960 KB Output is correct
17 Correct 1710 ms 17964 KB Output is correct
18 Correct 1308 ms 19908 KB Output is correct
19 Correct 1302 ms 16800 KB Output is correct
20 Correct 1414 ms 18512 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3168 KB Output is correct
2 Correct 142 ms 3172 KB Output is correct
3 Correct 150 ms 3176 KB Output is correct
4 Correct 143 ms 3172 KB Output is correct
5 Correct 135 ms 3180 KB Output is correct
6 Correct 145 ms 3168 KB Output is correct
7 Correct 170 ms 3140 KB Output is correct
8 Correct 150 ms 3172 KB Output is correct
9 Correct 133 ms 3172 KB Output is correct
10 Correct 138 ms 3168 KB Output is correct
11 Correct 1519 ms 18848 KB Output is correct
12 Correct 1483 ms 18568 KB Output is correct
13 Correct 1646 ms 17772 KB Output is correct
14 Correct 1614 ms 17888 KB Output is correct
15 Correct 1524 ms 18828 KB Output is correct
16 Correct 1605 ms 17960 KB Output is correct
17 Correct 1710 ms 17964 KB Output is correct
18 Correct 1308 ms 19908 KB Output is correct
19 Correct 1302 ms 16800 KB Output is correct
20 Correct 1414 ms 18512 KB Output is correct
21 Correct 1469 ms 22816 KB Output is correct
22 Correct 1560 ms 19028 KB Output is correct
23 Execution timed out 2029 ms 22048 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3168 KB Output is correct
2 Correct 142 ms 3172 KB Output is correct
3 Correct 150 ms 3176 KB Output is correct
4 Correct 143 ms 3172 KB Output is correct
5 Correct 135 ms 3180 KB Output is correct
6 Correct 145 ms 3168 KB Output is correct
7 Correct 170 ms 3140 KB Output is correct
8 Correct 150 ms 3172 KB Output is correct
9 Correct 133 ms 3172 KB Output is correct
10 Correct 138 ms 3168 KB Output is correct
11 Correct 208 ms 9200 KB Output is correct
12 Correct 249 ms 9212 KB Output is correct
13 Correct 250 ms 9316 KB Output is correct
14 Correct 254 ms 9384 KB Output is correct
15 Correct 306 ms 9452 KB Output is correct
16 Correct 289 ms 9300 KB Output is correct
17 Correct 275 ms 9332 KB Output is correct
18 Correct 216 ms 9096 KB Output is correct
19 Correct 219 ms 9240 KB Output is correct
20 Correct 209 ms 9180 KB Output is correct
21 Correct 281 ms 9348 KB Output is correct
22 Correct 261 ms 9332 KB Output is correct
23 Correct 306 ms 9332 KB Output is correct
24 Correct 263 ms 9372 KB Output is correct
25 Correct 263 ms 9380 KB Output is correct
26 Correct 215 ms 9100 KB Output is correct
27 Correct 226 ms 9124 KB Output is correct
28 Correct 228 ms 9216 KB Output is correct
29 Correct 286 ms 9328 KB Output is correct
30 Correct 253 ms 9332 KB Output is correct
31 Correct 241 ms 9236 KB Output is correct
32 Correct 266 ms 9356 KB Output is correct
33 Correct 264 ms 9312 KB Output is correct
34 Correct 186 ms 9060 KB Output is correct
35 Correct 299 ms 9316 KB Output is correct
36 Correct 279 ms 9328 KB Output is correct
37 Correct 284 ms 9444 KB Output is correct
38 Correct 280 ms 9324 KB Output is correct
39 Correct 280 ms 9444 KB Output is correct
40 Correct 280 ms 9444 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3168 KB Output is correct
2 Correct 142 ms 3172 KB Output is correct
3 Correct 150 ms 3176 KB Output is correct
4 Correct 143 ms 3172 KB Output is correct
5 Correct 135 ms 3180 KB Output is correct
6 Correct 145 ms 3168 KB Output is correct
7 Correct 170 ms 3140 KB Output is correct
8 Correct 150 ms 3172 KB Output is correct
9 Correct 133 ms 3172 KB Output is correct
10 Correct 138 ms 3168 KB Output is correct
11 Correct 1519 ms 18848 KB Output is correct
12 Correct 1483 ms 18568 KB Output is correct
13 Correct 1646 ms 17772 KB Output is correct
14 Correct 1614 ms 17888 KB Output is correct
15 Correct 1524 ms 18828 KB Output is correct
16 Correct 1605 ms 17960 KB Output is correct
17 Correct 1710 ms 17964 KB Output is correct
18 Correct 1308 ms 19908 KB Output is correct
19 Correct 1302 ms 16800 KB Output is correct
20 Correct 1414 ms 18512 KB Output is correct
21 Correct 1469 ms 22816 KB Output is correct
22 Correct 1560 ms 19028 KB Output is correct
23 Execution timed out 2029 ms 22048 KB Time limit exceeded
24 Halted 0 ms 0 KB -