oj.uz

Submission #399865

# Submission time Handle Problem Language Result Execution time Memory
399865 2021-05-06T18:33:07 Z MarcoMeijer Snake Escaping (JOI18_snake_escaping) C++14
65 / 100
 2000 ms 42076 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 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 584 ms 25244 KB Output is correct
2 Correct 598 ms 25328 KB Output is correct
3 Correct 589 ms 25308 KB Output is correct
4 Correct 587 ms 25284 KB Output is correct
5 Correct 594 ms 25344 KB Output is correct
6 Correct 584 ms 25280 KB Output is correct
7 Correct 584 ms 25360 KB Output is correct
8 Correct 586 ms 25352 KB Output is correct
9 Correct 592 ms 25428 KB Output is correct
10 Correct 592 ms 25296 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 25244 KB Output is correct
2 Correct 598 ms 25328 KB Output is correct
3 Correct 589 ms 25308 KB Output is correct
4 Correct 587 ms 25284 KB Output is correct
5 Correct 594 ms 25344 KB Output is correct
6 Correct 584 ms 25280 KB Output is correct
7 Correct 584 ms 25360 KB Output is correct
8 Correct 586 ms 25352 KB Output is correct
9 Correct 592 ms 25428 KB Output is correct
10 Correct 592 ms 25296 KB Output is correct
11 Correct 1133 ms 41104 KB Output is correct
12 Correct 1153 ms 40664 KB Output is correct
13 Correct 1182 ms 39904 KB Output is correct
14 Correct 1189 ms 40052 KB Output is correct
15 Correct 1185 ms 41056 KB Output is correct
16 Correct 1245 ms 40172 KB Output is correct
17 Correct 1264 ms 40176 KB Output is correct
18 Correct 1158 ms 42076 KB Output is correct
19 Correct 1183 ms 39004 KB Output is correct
20 Correct 1263 ms 40764 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 25244 KB Output is correct
2 Correct 598 ms 25328 KB Output is correct
3 Correct 589 ms 25308 KB Output is correct
4 Correct 587 ms 25284 KB Output is correct
5 Correct 594 ms 25344 KB Output is correct
6 Correct 584 ms 25280 KB Output is correct
7 Correct 584 ms 25360 KB Output is correct
8 Correct 586 ms 25352 KB Output is correct
9 Correct 592 ms 25428 KB Output is correct
10 Correct 592 ms 25296 KB Output is correct
11 Correct 1133 ms 41104 KB Output is correct
12 Correct 1153 ms 40664 KB Output is correct
13 Correct 1182 ms 39904 KB Output is correct
14 Correct 1189 ms 40052 KB Output is correct
15 Correct 1185 ms 41056 KB Output is correct
16 Correct 1245 ms 40172 KB Output is correct
17 Correct 1264 ms 40176 KB Output is correct
18 Correct 1158 ms 42076 KB Output is correct
19 Correct 1183 ms 39004 KB Output is correct
20 Correct 1263 ms 40764 KB Output is correct
21 Correct 1286 ms 41056 KB Output is correct
22 Correct 1362 ms 41304 KB Output is correct
23 Execution timed out 2025 ms 40332 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 25244 KB Output is correct
2 Correct 598 ms 25328 KB Output is correct
3 Correct 589 ms 25308 KB Output is correct
4 Correct 587 ms 25284 KB Output is correct
5 Correct 594 ms 25344 KB Output is correct
6 Correct 584 ms 25280 KB Output is correct
7 Correct 584 ms 25360 KB Output is correct
8 Correct 586 ms 25352 KB Output is correct
9 Correct 592 ms 25428 KB Output is correct
10 Correct 592 ms 25296 KB Output is correct
11 Correct 676 ms 31316 KB Output is correct
12 Correct 646 ms 31408 KB Output is correct
13 Correct 720 ms 31520 KB Output is correct
14 Correct 754 ms 31528 KB Output is correct
15 Correct 686 ms 31644 KB Output is correct
16 Correct 732 ms 31512 KB Output is correct
17 Correct 735 ms 31508 KB Output is correct
18 Correct 651 ms 31368 KB Output is correct
19 Correct 642 ms 31396 KB Output is correct
20 Correct 686 ms 31544 KB Output is correct
21 Correct 702 ms 31508 KB Output is correct
22 Correct 732 ms 31456 KB Output is correct
23 Correct 664 ms 31508 KB Output is correct
24 Correct 781 ms 31560 KB Output is correct
25 Correct 713 ms 31476 KB Output is correct
26 Correct 666 ms 31288 KB Output is correct
27 Correct 681 ms 31332 KB Output is correct
28 Correct 644 ms 31384 KB Output is correct
29 Correct 708 ms 31520 KB Output is correct
30 Correct 706 ms 31580 KB Output is correct
31 Correct 696 ms 31504 KB Output is correct
32 Correct 709 ms 31560 KB Output is correct
33 Correct 726 ms 31500 KB Output is correct
34 Correct 643 ms 31184 KB Output is correct
35 Correct 703 ms 31576 KB Output is correct
36 Correct 691 ms 31588 KB Output is correct
37 Correct 688 ms 31508 KB Output is correct
38 Correct 691 ms 31508 KB Output is correct
39 Correct 718 ms 31560 KB Output is correct
40 Correct 706 ms 31520 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 25244 KB Output is correct
2 Correct 598 ms 25328 KB Output is correct
3 Correct 589 ms 25308 KB Output is correct
4 Correct 587 ms 25284 KB Output is correct
5 Correct 594 ms 25344 KB Output is correct
6 Correct 584 ms 25280 KB Output is correct
7 Correct 584 ms 25360 KB Output is correct
8 Correct 586 ms 25352 KB Output is correct
9 Correct 592 ms 25428 KB Output is correct
10 Correct 592 ms 25296 KB Output is correct
11 Correct 1133 ms 41104 KB Output is correct
12 Correct 1153 ms 40664 KB Output is correct
13 Correct 1182 ms 39904 KB Output is correct
14 Correct 1189 ms 40052 KB Output is correct
15 Correct 1185 ms 41056 KB Output is correct
16 Correct 1245 ms 40172 KB Output is correct
17 Correct 1264 ms 40176 KB Output is correct
18 Correct 1158 ms 42076 KB Output is correct
19 Correct 1183 ms 39004 KB Output is correct
20 Correct 1263 ms 40764 KB Output is correct
21 Correct 1286 ms 41056 KB Output is correct
22 Correct 1362 ms 41304 KB Output is correct
23 Execution timed out 2025 ms 40332 KB Time limit exceeded
24 Halted 0 ms 0 KB -