oj.uz

Submission #437223

# Submission time Handle Problem Language Result Execution time Memory
437223 2021-06-26T05:11:24 Z cpp219 Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 17884 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 << 1) + 1; fQ(pos + 1); now = ((now - 1) >> 1);
    }
    else if (s[pos] == '0'){
        now <<= 1; fQ(pos + 1); now >>= 1;
    }
    else{
        now <<= 1; fQ(pos + 1); now >>= 1;
        now = (now << 1) + 1; fQ(pos + 1); now = ((now - 1) >> 1);
    }
}

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

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

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 284 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 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 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 284 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 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 277 ms 4312 KB Output is correct
12 Correct 330 ms 3980 KB Output is correct
13 Correct 444 ms 3160 KB Output is correct
14 Correct 613 ms 3276 KB Output is correct
15 Correct 427 ms 4256 KB Output is correct
16 Correct 575 ms 3488 KB Output is correct
17 Correct 515 ms 3728 KB Output is correct
18 Correct 249 ms 5296 KB Output is correct
19 Correct 279 ms 2252 KB Output is correct
20 Correct 295 ms 4036 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 284 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 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 277 ms 4312 KB Output is correct
12 Correct 330 ms 3980 KB Output is correct
13 Correct 444 ms 3160 KB Output is correct
14 Correct 613 ms 3276 KB Output is correct
15 Correct 427 ms 4256 KB Output is correct
16 Correct 575 ms 3488 KB Output is correct
17 Correct 515 ms 3728 KB Output is correct
18 Correct 249 ms 5296 KB Output is correct
19 Correct 279 ms 2252 KB Output is correct
20 Correct 295 ms 4036 KB Output is correct
21 Correct 395 ms 4332 KB Output is correct
22 Correct 393 ms 4672 KB Output is correct
23 Correct 709 ms 3660 KB Output is correct
24 Correct 927 ms 3516 KB Output is correct
25 Correct 525 ms 5356 KB Output is correct
26 Correct 861 ms 3948 KB Output is correct
27 Correct 734 ms 3792 KB Output is correct
28 Correct 256 ms 6392 KB Output is correct
29 Correct 350 ms 2484 KB Output is correct
30 Correct 377 ms 4680 KB Output is correct
31 Correct 652 ms 4536 KB Output is correct
32 Correct 1008 ms 4608 KB Output is correct
33 Correct 530 ms 3324 KB Output is correct
34 Correct 819 ms 3412 KB Output is correct
35 Correct 732 ms 3816 KB Output is correct
36 Correct 245 ms 2360 KB Output is correct
37 Correct 353 ms 4396 KB Output is correct
38 Correct 374 ms 2400 KB Output is correct
39 Correct 669 ms 3664 KB Output is correct
40 Correct 917 ms 3376 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 284 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 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 95 ms 12924 KB Output is correct
12 Correct 94 ms 12828 KB Output is correct
13 Correct 144 ms 12736 KB Output is correct
14 Correct 198 ms 12760 KB Output is correct
15 Correct 109 ms 12868 KB Output is correct
16 Correct 275 ms 12812 KB Output is correct
17 Correct 208 ms 12776 KB Output is correct
18 Correct 84 ms 13040 KB Output is correct
19 Correct 97 ms 12620 KB Output is correct
20 Correct 93 ms 12860 KB Output is correct
21 Correct 156 ms 12860 KB Output is correct
22 Correct 225 ms 12788 KB Output is correct
23 Correct 113 ms 12732 KB Output is correct
24 Correct 281 ms 12776 KB Output is correct
25 Correct 209 ms 12760 KB Output is correct
26 Correct 80 ms 12652 KB Output is correct
27 Correct 97 ms 12752 KB Output is correct
28 Correct 110 ms 12608 KB Output is correct
29 Correct 150 ms 12736 KB Output is correct
30 Correct 207 ms 12780 KB Output is correct
31 Correct 115 ms 12868 KB Output is correct
32 Correct 217 ms 12796 KB Output is correct
33 Correct 219 ms 12748 KB Output is correct
34 Correct 106 ms 12600 KB Output is correct
35 Correct 168 ms 12692 KB Output is correct
36 Correct 159 ms 12824 KB Output is correct
37 Correct 171 ms 12692 KB Output is correct
38 Correct 181 ms 12768 KB Output is correct
39 Correct 166 ms 12804 KB Output is correct
40 Correct 164 ms 12872 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 284 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 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 277 ms 4312 KB Output is correct
12 Correct 330 ms 3980 KB Output is correct
13 Correct 444 ms 3160 KB Output is correct
14 Correct 613 ms 3276 KB Output is correct
15 Correct 427 ms 4256 KB Output is correct
16 Correct 575 ms 3488 KB Output is correct
17 Correct 515 ms 3728 KB Output is correct
18 Correct 249 ms 5296 KB Output is correct
19 Correct 279 ms 2252 KB Output is correct
20 Correct 295 ms 4036 KB Output is correct
21 Correct 395 ms 4332 KB Output is correct
22 Correct 393 ms 4672 KB Output is correct
23 Correct 709 ms 3660 KB Output is correct
24 Correct 927 ms 3516 KB Output is correct
25 Correct 525 ms 5356 KB Output is correct
26 Correct 861 ms 3948 KB Output is correct
27 Correct 734 ms 3792 KB Output is correct
28 Correct 256 ms 6392 KB Output is correct
29 Correct 350 ms 2484 KB Output is correct
30 Correct 377 ms 4680 KB Output is correct
31 Correct 652 ms 4536 KB Output is correct
32 Correct 1008 ms 4608 KB Output is correct
33 Correct 530 ms 3324 KB Output is correct
34 Correct 819 ms 3412 KB Output is correct
35 Correct 732 ms 3816 KB Output is correct
36 Correct 245 ms 2360 KB Output is correct
37 Correct 353 ms 4396 KB Output is correct
38 Correct 374 ms 2400 KB Output is correct
39 Correct 669 ms 3664 KB Output is correct
40 Correct 917 ms 3376 KB Output is correct
41 Correct 95 ms 12924 KB Output is correct
42 Correct 94 ms 12828 KB Output is correct
43 Correct 144 ms 12736 KB Output is correct
44 Correct 198 ms 12760 KB Output is correct
45 Correct 109 ms 12868 KB Output is correct
46 Correct 275 ms 12812 KB Output is correct
47 Correct 208 ms 12776 KB Output is correct
48 Correct 84 ms 13040 KB Output is correct
49 Correct 97 ms 12620 KB Output is correct
50 Correct 93 ms 12860 KB Output is correct
51 Correct 156 ms 12860 KB Output is correct
52 Correct 225 ms 12788 KB Output is correct
53 Correct 113 ms 12732 KB Output is correct
54 Correct 281 ms 12776 KB Output is correct
55 Correct 209 ms 12760 KB Output is correct
56 Correct 80 ms 12652 KB Output is correct
57 Correct 97 ms 12752 KB Output is correct
58 Correct 110 ms 12608 KB Output is correct
59 Correct 150 ms 12736 KB Output is correct
60 Correct 207 ms 12780 KB Output is correct
61 Correct 115 ms 12868 KB Output is correct
62 Correct 217 ms 12796 KB Output is correct
63 Correct 219 ms 12748 KB Output is correct
64 Correct 106 ms 12600 KB Output is correct
65 Correct 168 ms 12692 KB Output is correct
66 Correct 159 ms 12824 KB Output is correct
67 Correct 171 ms 12692 KB Output is correct
68 Correct 181 ms 12768 KB Output is correct
69 Correct 166 ms 12804 KB Output is correct
70 Correct 164 ms 12872 KB Output is correct
71 Correct 603 ms 17724 KB Output is correct
72 Correct 648 ms 17884 KB Output is correct
73 Correct 1632 ms 16324 KB Output is correct
74 Execution timed out 2073 ms 15940 KB Time limit exceeded
75 Halted 0 ms 0 KB -