oj.uz

Submission #437222

# Submission time Handle Problem Language Result Execution time Memory
437222 2021-06-26T05:04:00 Z cpp219 Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 31508 KB 
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = (1 << 20) + 9;
const ll inf = 1e9 + 7;
char c;
string s;
ll a[N];
ll L,Q,dp[N],dpR[N];

bool bit(ll x,ll i){
    return (x >> i) & 1;
}

ll take,now,ans;

inline void fQ(ll pos){
    if (pos >= L){
        //cout<<now<<"x\n";
        ans += a[now]; return;
    }
    if (s[pos] == '1'){
        now = now*2 + 1; fQ(pos + 1); now = (now - 1)/2;
    }
    else if (s[pos] == '0'){
        now = now*2; fQ(pos + 1); now /= 2;
    }
    else{
        now = now*2; fQ(pos + 1); now /= 2;
        now = now*2 + 1; fQ(pos + 1); now = (now - 1)/2;
    }
}

inline void f1(ll pos){
    if (pos >= L){
        //cout<<now<<"x\n";
        if (take%2 == 0) ans += dp[now];
        else ans -= dp[now];
        return;
    }
    if (s[pos] == '1'){
        now = now*2; take++; f1(pos + 1); now /= 2; take--;
        now = now*2 + 1; f1(pos + 1); now = (now - 1)/2;
    }
    else if (s[pos] == '0'){
        now = now*2; f1(pos + 1); now /= 2;
    }
    else{
        now = now*2 + 1; f1(pos + 1); now = (now - 1)/2;
    }
}

inline void f0(ll pos){
    if (pos >= L){
        if (take%2 == 0) ans += dpR[now];
        else ans -= dpR[now];
        return;
    }
    if (s[pos] == '1'){
        now = now*2 + 1; f0(pos + 1); now = (now - 1)/2;
    }
    else if (s[pos] == '0'){
        now = now*2 + 1; take++; f0(pos + 1); now = (now - 1)/2; take--;
        now = now*2; f0(pos + 1); now /= 2;
    }
    else{
        now = now*2; f0(pos + 1); now /= 2;
    }
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>L>>Q;
    for (ll i = 0;i < (1 << L);i++){
        cin>>c; a[i] = c - '0';
        dp[i] += a[i]; dpR[i] += a[i];
    }

    for (ll i = 0;i < L;i++){
        for (ll mask = 0;mask < (1 << L);mask++)
            if (bit(mask,i)) dp[mask] += dp[mask ^ (1 << i)];
        for (ll mask = (1 << L) - 1;mask >= 0;mask--)
            if (!bit(mask,i)) dpR[mask] += dpR[mask ^ (1 << i)];
    }

    while(Q--){
        cin>>s; ll cnt1 = 0,cnt0 = 0,cntQ = 0; take = now = ans = 0;
        for (ll i = 0;i < L;i++){
            if (s[i] == '1') cnt1++;
            else if (s[i] == '0') cnt0++;
            else cntQ++;
        }
        ll mn = min(cntQ,min(cnt1,cnt0));
        if (cntQ == mn) fQ(0);
        else if (cnt1 == mn) f1(0);
        else f0(0);
        cout<<ans<<"\n";
    }
}

Compilation message

snake_escaping.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
snake_escaping.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
snake_escaping.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 284 ms 4268 KB Output is correct
12 Correct 318 ms 3908 KB Output is correct
13 Correct 443 ms 3392 KB Output is correct
14 Correct 573 ms 3444 KB Output is correct
15 Correct 375 ms 4292 KB Output is correct
16 Correct 538 ms 3556 KB Output is correct
17 Correct 527 ms 3524 KB Output is correct
18 Correct 238 ms 5408 KB Output is correct
19 Correct 280 ms 2220 KB Output is correct
20 Correct 304 ms 4088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 284 ms 4268 KB Output is correct
12 Correct 318 ms 3908 KB Output is correct
13 Correct 443 ms 3392 KB Output is correct
14 Correct 573 ms 3444 KB Output is correct
15 Correct 375 ms 4292 KB Output is correct
16 Correct 538 ms 3556 KB Output is correct
17 Correct 527 ms 3524 KB Output is correct
18 Correct 238 ms 5408 KB Output is correct
19 Correct 280 ms 2220 KB Output is correct
20 Correct 304 ms 4088 KB Output is correct
21 Correct 342 ms 4348 KB Output is correct
22 Correct 391 ms 4544 KB Output is correct
23 Correct 650 ms 3532 KB Output is correct
24 Correct 956 ms 3428 KB Output is correct
25 Correct 482 ms 5432 KB Output is correct
26 Correct 825 ms 4036 KB Output is correct
27 Correct 742 ms 3780 KB Output is correct
28 Correct 264 ms 6340 KB Output is correct
29 Correct 361 ms 2372 KB Output is correct
30 Correct 376 ms 4580 KB Output is correct
31 Correct 628 ms 4416 KB Output is correct
32 Correct 901 ms 4520 KB Output is correct
33 Correct 532 ms 3456 KB Output is correct
34 Correct 837 ms 3640 KB Output is correct
35 Correct 767 ms 3996 KB Output is correct
36 Correct 256 ms 2460 KB Output is correct
37 Correct 356 ms 4420 KB Output is correct
38 Correct 408 ms 2316 KB Output is correct
39 Correct 678 ms 3992 KB Output is correct
40 Correct 952 ms 3380 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 94 ms 12808 KB Output is correct
12 Correct 100 ms 12860 KB Output is correct
13 Correct 149 ms 12744 KB Output is correct
14 Correct 205 ms 12744 KB Output is correct
15 Correct 109 ms 12824 KB Output is correct
16 Correct 234 ms 12776 KB Output is correct
17 Correct 208 ms 12756 KB Output is correct
18 Correct 83 ms 12996 KB Output is correct
19 Correct 101 ms 12688 KB Output is correct
20 Correct 103 ms 12868 KB Output is correct
21 Correct 147 ms 12856 KB Output is correct
22 Correct 199 ms 12740 KB Output is correct
23 Correct 114 ms 12736 KB Output is correct
24 Correct 214 ms 12768 KB Output is correct
25 Correct 212 ms 12732 KB Output is correct
26 Correct 86 ms 12612 KB Output is correct
27 Correct 99 ms 12740 KB Output is correct
28 Correct 99 ms 12604 KB Output is correct
29 Correct 169 ms 12896 KB Output is correct
30 Correct 220 ms 12688 KB Output is correct
31 Correct 110 ms 12732 KB Output is correct
32 Correct 227 ms 12740 KB Output is correct
33 Correct 202 ms 12864 KB Output is correct
34 Correct 84 ms 12612 KB Output is correct
35 Correct 163 ms 12748 KB Output is correct
36 Correct 165 ms 12760 KB Output is correct
37 Correct 165 ms 12816 KB Output is correct
38 Correct 167 ms 12728 KB Output is correct
39 Correct 176 ms 12740 KB Output is correct
40 Correct 169 ms 12776 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 284 ms 4268 KB Output is correct
12 Correct 318 ms 3908 KB Output is correct
13 Correct 443 ms 3392 KB Output is correct
14 Correct 573 ms 3444 KB Output is correct
15 Correct 375 ms 4292 KB Output is correct
16 Correct 538 ms 3556 KB Output is correct
17 Correct 527 ms 3524 KB Output is correct
18 Correct 238 ms 5408 KB Output is correct
19 Correct 280 ms 2220 KB Output is correct
20 Correct 304 ms 4088 KB Output is correct
21 Correct 342 ms 4348 KB Output is correct
22 Correct 391 ms 4544 KB Output is correct
23 Correct 650 ms 3532 KB Output is correct
24 Correct 956 ms 3428 KB Output is correct
25 Correct 482 ms 5432 KB Output is correct
26 Correct 825 ms 4036 KB Output is correct
27 Correct 742 ms 3780 KB Output is correct
28 Correct 264 ms 6340 KB Output is correct
29 Correct 361 ms 2372 KB Output is correct
30 Correct 376 ms 4580 KB Output is correct
31 Correct 628 ms 4416 KB Output is correct
32 Correct 901 ms 4520 KB Output is correct
33 Correct 532 ms 3456 KB Output is correct
34 Correct 837 ms 3640 KB Output is correct
35 Correct 767 ms 3996 KB Output is correct
36 Correct 256 ms 2460 KB Output is correct
37 Correct 356 ms 4420 KB Output is correct
38 Correct 408 ms 2316 KB Output is correct
39 Correct 678 ms 3992 KB Output is correct
40 Correct 952 ms 3380 KB Output is correct
41 Correct 94 ms 12808 KB Output is correct
42 Correct 100 ms 12860 KB Output is correct
43 Correct 149 ms 12744 KB Output is correct
44 Correct 205 ms 12744 KB Output is correct
45 Correct 109 ms 12824 KB Output is correct
46 Correct 234 ms 12776 KB Output is correct
47 Correct 208 ms 12756 KB Output is correct
48 Correct 83 ms 12996 KB Output is correct
49 Correct 101 ms 12688 KB Output is correct
50 Correct 103 ms 12868 KB Output is correct
51 Correct 147 ms 12856 KB Output is correct
52 Correct 199 ms 12740 KB Output is correct
53 Correct 114 ms 12736 KB Output is correct
54 Correct 214 ms 12768 KB Output is correct
55 Correct 212 ms 12732 KB Output is correct
56 Correct 86 ms 12612 KB Output is correct
57 Correct 99 ms 12740 KB Output is correct
58 Correct 99 ms 12604 KB Output is correct
59 Correct 169 ms 12896 KB Output is correct
60 Correct 220 ms 12688 KB Output is correct
61 Correct 110 ms 12732 KB Output is correct
62 Correct 227 ms 12740 KB Output is correct
63 Correct 202 ms 12864 KB Output is correct
64 Correct 84 ms 12612 KB Output is correct
65 Correct 163 ms 12748 KB Output is correct
66 Correct 165 ms 12760 KB Output is correct
67 Correct 165 ms 12816 KB Output is correct
68 Correct 167 ms 12728 KB Output is correct
69 Correct 176 ms 12740 KB Output is correct
70 Correct 169 ms 12776 KB Output is correct
71 Correct 635 ms 17688 KB Output is correct
72 Correct 631 ms 17756 KB Output is correct
73 Correct 1617 ms 16240 KB Output is correct
74 Execution timed out 2029 ms 31508 KB Time limit exceeded
75 Halted 0 ms 0 KB -