oj.uz

답안 #1095736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095736 2024-10-03T04:06:36 Z doducanh Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 563 ms 51560 KB 
///breaker
///every second counts
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
int l,q;
string s;
ll f0[(1<<20)];
ll f1[(1<<20)];
int cnt[(1<<20)];
void sol(void){
    cin>>l>>q;
    cin>>s;
    for(int i=0;i<s.size();i++){
        f0[i]+=s[i]-'0';
        f1[i]+=s[i]-'0';
    }
    for(int i=0;i<20;i++){
        for(int j=0;j<(1<<20);j++)if(bit(j,i)){
            f0[j]+=f0[(j^(1<<i))];
            f1[(j^(1<<i))]+=f1[j];
        }
    }
    for(int i=0;i<(1<<20);i++){
        cnt[i]=__builtin_popcount(i);
    }
    while(q--){
        string tmp;
        cin>>tmp;
        reverse(tmp.begin(),tmp.end());
        int a=0,b=0,c=0;
        for(int i=0;i<l;i++){
            if(tmp[i]=='0'){
                a|=(1<<i);
            }
            else if(tmp[i]=='1'){
                b|=(1<<i);
            }
            else c|=(1<<i);
        }
        ll res=0;
        if(cnt[c]<=l/3){
            for(int i=c;i>=0;i--){
                i&=c;
                res+=(s[i|b]-'0');
            }
        }
        else if(cnt[a]<=l/3){
            for(int i=a;i>=0;i--){
                i&=a;
                if(cnt[i]&1){
                    res-=f1[i|b];
                }
                else res+=f1[i|b];
            }
        }
        else{
            for(int i=b;i>=0;i--){
                i&=b;
                if((cnt[b]-cnt[i])&1)res-=f0[i|c];
                else res+=f0[i|c];
            }
        }
        cout<<res<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message

snake_escaping.cpp: In function 'void sol()':
snake_escaping.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 20828 KB Output is correct
2 Correct 28 ms 20820 KB Output is correct
3 Correct 29 ms 20820 KB Output is correct
4 Correct 29 ms 20724 KB Output is correct
5 Correct 29 ms 20844 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 29 ms 20828 KB Output is correct
8 Correct 28 ms 20816 KB Output is correct
9 Correct 30 ms 20820 KB Output is correct
10 Correct 29 ms 20820 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 20828 KB Output is correct
2 Correct 28 ms 20820 KB Output is correct
3 Correct 29 ms 20820 KB Output is correct
4 Correct 29 ms 20724 KB Output is correct
5 Correct 29 ms 20844 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 29 ms 20828 KB Output is correct
8 Correct 28 ms 20816 KB Output is correct
9 Correct 30 ms 20820 KB Output is correct
10 Correct 29 ms 20820 KB Output is correct
11 Correct 165 ms 34656 KB Output is correct
12 Correct 171 ms 34316 KB Output is correct
13 Correct 187 ms 33364 KB Output is correct
14 Correct 181 ms 33620 KB Output is correct
15 Correct 178 ms 34640 KB Output is correct
16 Correct 201 ms 33780 KB Output is correct
17 Correct 198 ms 33620 KB Output is correct
18 Correct 152 ms 35540 KB Output is correct
19 Correct 170 ms 32532 KB Output is correct
20 Correct 182 ms 34152 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 20828 KB Output is correct
2 Correct 28 ms 20820 KB Output is correct
3 Correct 29 ms 20820 KB Output is correct
4 Correct 29 ms 20724 KB Output is correct
5 Correct 29 ms 20844 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 29 ms 20828 KB Output is correct
8 Correct 28 ms 20816 KB Output is correct
9 Correct 30 ms 20820 KB Output is correct
10 Correct 29 ms 20820 KB Output is correct
11 Correct 165 ms 34656 KB Output is correct
12 Correct 171 ms 34316 KB Output is correct
13 Correct 187 ms 33364 KB Output is correct
14 Correct 181 ms 33620 KB Output is correct
15 Correct 178 ms 34640 KB Output is correct
16 Correct 201 ms 33780 KB Output is correct
17 Correct 198 ms 33620 KB Output is correct
18 Correct 152 ms 35540 KB Output is correct
19 Correct 170 ms 32532 KB Output is correct
20 Correct 182 ms 34152 KB Output is correct
21 Correct 190 ms 37352 KB Output is correct
22 Correct 209 ms 37604 KB Output is correct
23 Correct 239 ms 36692 KB Output is correct
24 Correct 243 ms 36436 KB Output is correct
25 Correct 215 ms 38448 KB Output is correct
26 Correct 239 ms 37020 KB Output is correct
27 Correct 253 ms 36976 KB Output is correct
28 Correct 145 ms 39496 KB Output is correct
29 Correct 202 ms 35412 KB Output is correct
30 Correct 215 ms 37656 KB Output is correct
31 Correct 238 ms 37608 KB Output is correct
32 Correct 247 ms 37408 KB Output is correct
33 Correct 216 ms 36428 KB Output is correct
34 Correct 230 ms 36436 KB Output is correct
35 Correct 264 ms 36800 KB Output is correct
36 Correct 151 ms 35412 KB Output is correct
37 Correct 222 ms 37708 KB Output is correct
38 Correct 205 ms 35412 KB Output is correct
39 Correct 230 ms 36608 KB Output is correct
40 Correct 236 ms 36436 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 20828 KB Output is correct
2 Correct 28 ms 20820 KB Output is correct
3 Correct 29 ms 20820 KB Output is correct
4 Correct 29 ms 20724 KB Output is correct
5 Correct 29 ms 20844 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 29 ms 20828 KB Output is correct
8 Correct 28 ms 20816 KB Output is correct
9 Correct 30 ms 20820 KB Output is correct
10 Correct 29 ms 20820 KB Output is correct
11 Correct 49 ms 24416 KB Output is correct
12 Correct 50 ms 24376 KB Output is correct
13 Correct 52 ms 24124 KB Output is correct
14 Correct 57 ms 24308 KB Output is correct
15 Correct 47 ms 24416 KB Output is correct
16 Correct 59 ms 24312 KB Output is correct
17 Correct 52 ms 24308 KB Output is correct
18 Correct 37 ms 24416 KB Output is correct
19 Correct 55 ms 24048 KB Output is correct
20 Correct 49 ms 24304 KB Output is correct
21 Correct 56 ms 24180 KB Output is correct
22 Correct 69 ms 24308 KB Output is correct
23 Correct 47 ms 24308 KB Output is correct
24 Correct 51 ms 24304 KB Output is correct
25 Correct 50 ms 24312 KB Output is correct
26 Correct 38 ms 24116 KB Output is correct
27 Correct 46 ms 24248 KB Output is correct
28 Correct 53 ms 24212 KB Output is correct
29 Correct 49 ms 24308 KB Output is correct
30 Correct 49 ms 24308 KB Output is correct
31 Correct 48 ms 24312 KB Output is correct
32 Correct 55 ms 24308 KB Output is correct
33 Correct 54 ms 24164 KB Output is correct
34 Correct 39 ms 24052 KB Output is correct
35 Correct 50 ms 24304 KB Output is correct
36 Correct 50 ms 24308 KB Output is correct
37 Correct 49 ms 24308 KB Output is correct
38 Correct 51 ms 24220 KB Output is correct
39 Correct 72 ms 24308 KB Output is correct
40 Correct 51 ms 24304 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 20828 KB Output is correct
2 Correct 28 ms 20820 KB Output is correct
3 Correct 29 ms 20820 KB Output is correct
4 Correct 29 ms 20724 KB Output is correct
5 Correct 29 ms 20844 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 29 ms 20828 KB Output is correct
8 Correct 28 ms 20816 KB Output is correct
9 Correct 30 ms 20820 KB Output is correct
10 Correct 29 ms 20820 KB Output is correct
11 Correct 165 ms 34656 KB Output is correct
12 Correct 171 ms 34316 KB Output is correct
13 Correct 187 ms 33364 KB Output is correct
14 Correct 181 ms 33620 KB Output is correct
15 Correct 178 ms 34640 KB Output is correct
16 Correct 201 ms 33780 KB Output is correct
17 Correct 198 ms 33620 KB Output is correct
18 Correct 152 ms 35540 KB Output is correct
19 Correct 170 ms 32532 KB Output is correct
20 Correct 182 ms 34152 KB Output is correct
21 Correct 190 ms 37352 KB Output is correct
22 Correct 209 ms 37604 KB Output is correct
23 Correct 239 ms 36692 KB Output is correct
24 Correct 243 ms 36436 KB Output is correct
25 Correct 215 ms 38448 KB Output is correct
26 Correct 239 ms 37020 KB Output is correct
27 Correct 253 ms 36976 KB Output is correct
28 Correct 145 ms 39496 KB Output is correct
29 Correct 202 ms 35412 KB Output is correct
30 Correct 215 ms 37656 KB Output is correct
31 Correct 238 ms 37608 KB Output is correct
32 Correct 247 ms 37408 KB Output is correct
33 Correct 216 ms 36428 KB Output is correct
34 Correct 230 ms 36436 KB Output is correct
35 Correct 264 ms 36800 KB Output is correct
36 Correct 151 ms 35412 KB Output is correct
37 Correct 222 ms 37708 KB Output is correct
38 Correct 205 ms 35412 KB Output is correct
39 Correct 230 ms 36608 KB Output is correct
40 Correct 236 ms 36436 KB Output is correct
41 Correct 49 ms 24416 KB Output is correct
42 Correct 50 ms 24376 KB Output is correct
43 Correct 52 ms 24124 KB Output is correct
44 Correct 57 ms 24308 KB Output is correct
45 Correct 47 ms 24416 KB Output is correct
46 Correct 59 ms 24312 KB Output is correct
47 Correct 52 ms 24308 KB Output is correct
48 Correct 37 ms 24416 KB Output is correct
49 Correct 55 ms 24048 KB Output is correct
50 Correct 49 ms 24304 KB Output is correct
51 Correct 56 ms 24180 KB Output is correct
52 Correct 69 ms 24308 KB Output is correct
53 Correct 47 ms 24308 KB Output is correct
54 Correct 51 ms 24304 KB Output is correct
55 Correct 50 ms 24312 KB Output is correct
56 Correct 38 ms 24116 KB Output is correct
57 Correct 46 ms 24248 KB Output is correct
58 Correct 53 ms 24212 KB Output is correct
59 Correct 49 ms 24308 KB Output is correct
60 Correct 49 ms 24308 KB Output is correct
61 Correct 48 ms 24312 KB Output is correct
62 Correct 55 ms 24308 KB Output is correct
63 Correct 54 ms 24164 KB Output is correct
64 Correct 39 ms 24052 KB Output is correct
65 Correct 50 ms 24304 KB Output is correct
66 Correct 50 ms 24308 KB Output is correct
67 Correct 49 ms 24308 KB Output is correct
68 Correct 51 ms 24220 KB Output is correct
69 Correct 72 ms 24308 KB Output is correct
70 Correct 51 ms 24304 KB Output is correct
71 Correct 309 ms 47660 KB Output is correct
72 Correct 341 ms 48744 KB Output is correct
73 Correct 371 ms 47336 KB Output is correct
74 Correct 558 ms 47600 KB Output is correct
75 Correct 335 ms 49648 KB Output is correct
76 Correct 506 ms 47972 KB Output is correct
77 Correct 423 ms 47864 KB Output is correct
78 Correct 185 ms 51560 KB Output is correct
79 Correct 244 ms 45668 KB Output is correct
80 Correct 277 ms 48632 KB Output is correct
81 Correct 417 ms 48624 KB Output is correct
82 Correct 529 ms 47536 KB Output is correct
83 Correct 295 ms 46836 KB Output is correct
84 Correct 412 ms 47600 KB Output is correct
85 Correct 443 ms 47856 KB Output is correct
86 Correct 183 ms 45700 KB Output is correct
87 Correct 301 ms 48628 KB Output is correct
88 Correct 277 ms 45652 KB Output is correct
89 Correct 383 ms 47380 KB Output is correct
90 Correct 408 ms 47604 KB Output is correct
91 Correct 325 ms 46832 KB Output is correct
92 Correct 563 ms 48188 KB Output is correct
93 Correct 479 ms 47916 KB Output is correct
94 Correct 172 ms 45552 KB Output is correct
95 Correct 422 ms 47752 KB Output is correct
96 Correct 416 ms 47804 KB Output is correct
97 Correct 422 ms 47604 KB Output is correct
98 Correct 409 ms 47684 KB Output is correct
99 Correct 447 ms 47348 KB Output is correct
100 Correct 427 ms 47604 KB Output is correct