oj.uz

답안 #431860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431860 2021-06-17T16:21:27 Z hackerbhaiya Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 1 ms 332 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
#define ll long long
// #define ll ll
#define f(i,a,b) for(ll i=a;i<b;i++)
// #define mod 1000000007
#define mod 998244353
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf prllf
#define sz(a) (ll)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
// ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std; 

int n,q;
string s;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("gift1.in","r",stdin);
    // freopen("gift1.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    while(z--)
    {     
        cin>>n>>q>>s;
        int sup[1<<n|1],sub[1<<n|1],cnt[1<<n|1];
        for(int mask=0;mask<(1<<n);mask++)
            sub[mask]=sup[mask]=(s[mask]-'0'),cnt[mask]=__builtin_popcount(mask);
        f(i,0,n)
        {
            for(int mask=0;mask<(1<<n);mask++)
            {
                if(mask&(1<<i))
                    sub[mask]+=sub[mask^(1<<i)];
                else
                    sup[mask]+=sup[mask^(1<<i)];
            }
        }
        while(q--)
        {
            string str;
            cin>>str;
            reverse(all(str));
            int mask1=0,mask2=0,mask3=0;
            f(i,0,n)
            {
                if(str[i]=='?')
                    mask1|=(1<<i);
                else if(str[i]=='0')
                    mask2|=(1<<i);
                else
                    mask3|=(1<<i);
            }
            int ans=0;
            if(cnt[mask1]<=cnt[mask2] && cnt[mask1]<=cnt[mask3])
            {
                for(int submask=mask1;submask>0;submask=((submask-1)&mask1))
                    ans+=(s[mask3|submask]-'0');
                ans+=(s[mask3]-'0');
            }
            else if(cnt[mask2]<=cnt[mask3] && cnt[mask2]<=cnt[mask1])
            {
                for(int submask=mask2;submask>0;submask=(mask2&(submask-1)))
                    ans+=(((cnt[submask]&1)?-1:1)*sup[submask|mask3]);
                ans+=sup[mask3];
            }
            else
            {
                for(int submask=mask3;submask>0;submask=(mask3&(submask-1)))
                    ans+=(((cnt[submask]&1)?-1:1)*sub[submask|mask1]);
                ans+=sub[mask1];
            }
            cout<<ans<<"\n";
        }
    }       
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -