Submission #810538

#	Time	Username	Problem	Language	Result	Execution time	Memory
810538		lalala56	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	340 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define PROB "solve"
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;(i)++)
#define FOD(i,a,b) for(int i=a;i>=b;(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) int(x.size())
const int N=4e6+9,M=(1<<21)-1;
const ll mod=1e9+7;
int a[N],f[N],g[N];
int n;
bool bit(int p,int i){
    return (p>>i)&1;
}
void pp(){
    FOR(i,0,n-1)FOR(mask,0,(1<<n)-1){
        if(bit(mask,i))f[mask]+=f[mask^(1<<i)];
    }
    FOR(i,0,n-1)FOD(mask,(1<<n)-1,0){
        if(!bit(mask,i))g[mask]+=g[mask^(1<<i)];
    }
}
int so0(int s,int t) {
    int res=0;
    //cout<<s<<" "<<res<<"\n\n";
    for(int mask=t;;mask=(mask-1)&t){
        //cout<<mask<<" "<<(s|mask)<<" "<<g[s|mask]<<'\n';
        if(__builtin_popcount(mask)&1)res-=g[s|mask];
        else res+=g[s|mask];
        if(mask==0)break;
    }
    return res;
}
int so1(int s,int t){
    int res=0;
    for(int mask=t;;mask=(mask-1)&t){
        if(__builtin_popcount(mask)&1)res-=f[s^mask];
        else res+=f[s^mask];
        if(mask==0)break;
    }
    return res;
}
int so2(int s,int t){
    int res=0;
    for(int mask=t;;mask=(mask-1)&t){
        res+=a[s|mask];
        if(mask==0)break;
    }
    return res;
}
void giai(){
    int q;
    cin>>n>>q;
    FOR(i,0,(1<<n)-1){
        char x;cin>>x;
        a[i]=x-'0';
        f[i]+=x-'0';
        g[i]+=x-'0';
    }
    pp();
    FOR(i,1,q){
        int s[3]={0,0,0},u=0,u1,k[3]={0,0,0};
        FOR(j,0,n-1){
            char x;cin>>x;
            u*=2;
            FOR(t,0,2)k[t]*=2;
            if(x=='0'){
                s[0]++;
                k[0]++;
            }
            else if(x=='1'){
                s[1]++;
                u++;
                k[1]++;
            }
            else{
                s[2]++;
                k[2]++;
            }
        }
        //cout<<u<<" "<<k[0]<<" "<<k[1]<<" "<<k[2]<<'\n';
        if(s[0]<=6)cout<<so0(u,k[0])<<'\n';
        else if(s[1]<=6)so1(u|k[2],k[1])<<'\n';
        else cout<<so2(u,k[2])<<'\n';


    }
    

}
int main(){
    if(fopen(PROB".inp","r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    giai();

}

Compilation message (stderr)

snake_escaping.cpp: In function 'void giai()':
snake_escaping.cpp:86:41: warning: value computed is not used [-Wunused-value]
   86 |         else if(s[1]<=6)so1(u|k[2],k[1])<<'\n';
      |                         ~~~~~~~~~~~~~~~~^~~~~~
snake_escaping.cpp:65:30: warning: unused variable 'u1' [-Wunused-variable]
   65 |         int s[3]={0,0,0},u=0,u1,k[3]={0,0,0};
      |                              ^~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25