oj.uz

Submission #1095731

# Submission time Handle Problem Language Result Execution time Memory
1095731 2024-10-03T03:59:21 Z doducanh Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 26 ms 16732 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)];
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];
        }
    }
    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(__builtin_popcount(a)<=l/3){
            for(int i=a;i>=0;i--){
                i&=a;
                if(__builtin_popcount(i)==0){
                    res+=f1[i|b];
                }
                else res-=f1[i|b];
            }
        }
        else if(__builtin_popcount(b)<=l/3){
            for(int i=b;i>=0;i--){
                i&=b;
                if((__builtin_popcount(b)-__builtin_popcount(i)))res-=f0[i|c];
                else res+=f0[i|c];
            }
        }
        else{
            for(int i=c;i>=0;i--){
                i&=c;
                res+=(s[i|b]-'0');
            }
        }
        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:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Incorrect 26 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Incorrect 26 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Incorrect 26 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Incorrect 26 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16732 KB Output is correct
2 Incorrect 26 ms 16728 KB Output isn't correct
3 Halted 0 ms 0 KB -