oj.uz

Submission #939498

# Submission time Handle Problem Language Result Execution time Memory
939498 2024-03-06T12:05:40 Z vjudge1 Snake Escaping (JOI18_snake_escaping) C++17
75 / 100
 2000 ms 28148 KB 
#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll

const int MAX=1e5+15;
const int B=2e5;
const int N=104;
const int block=450;
const int maxB=MAX/B+10;
const ll inf=1e18;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1);
  int k=binpow(a,n/2);
  return k*k;
}

int n,q;
string s;
int dp1[(1<<21)];
int dp0[(1<<21)];

int bit(int i,int j){
  return (i>>j)&1;
}

int stupid(string t){
  int ans=0;
  int c=0;
  for(int j=0;j<n;j++)if(t[j]=='?')c++;
  for(int i=0;i<(1<<c);i++){
    int cur=0;
    int f=0;
    for(int j=0;j<n;j++){
      if(t[j]!='?'){
        f=f*2+(t[j]-'0');
      }
      else{
        f=f*2+bit(i,cur++);
      }
    }
    ans+=s[f]-'0';
  }
  return ans;
}

void solve(){
  cin>>n>>q;
  cin>>s;
  for(int mask=0;mask<(1<<n);mask++)dp1[mask]=s[mask]-'0';
  for(int i=0;i<=n;i++){
    for(int mask=(1<<n)-1;mask>=0;mask--){
      if(!((mask>>i)&1)){
        dp1[mask]+=dp1[mask+(1<<i)];
      }
    }
  }
  for(int mask=0;mask<(1<<n);mask++)dp0[mask]=s[mask]-'0';
  for(int i=0;i<n;i++){
    for(int mask=0;mask<(1<<n);mask++){
      if((mask>>i)&1){
        dp0[mask]+=dp0[mask-(1<<i)];
      }
    }
  }
  while(q--){
    string t;
    cin>>t;
    int c0=0,c1=0,c=0;
    for(int i=0;i<n;i++){
      if(t[i]=='0')c0++;
      else if(t[i]=='1')c1++;
      else c++;
    }
    if(c<=min(c1,c0)){
      cout<<stupid(t)<<"\n";
    }
    else if(c0<=c1){
      int ans=0;
      for(int mask=0;mask<(1<<c0);mask++){
        int f1=0;
        int cur=0;
        int c=0;
        for(int j=0;j<n;j++){
          if(t[j]=='1'){
            f1=f1*2+1;
          }
          else if(t[j]=='?'){
            f1=f1*2;
          }
          else{
            f1=f1*2;
            if(bit(mask,cur++)){
              f1++;
              c++;
            }
          }
        }
        int res=dp1[f1];
        if(c%2==1)ans-=res;
        else ans+=res;
      }
      cout<<ans<<"\n";
    }
    else{
      int ans=0;
      for(int mask=0;mask<(1<<c1);mask++){
        int f1=0;
        int cur=0;
        int c=0;
        for(int j=0;j<n;j++){
          if(t[j]=='0'){
            f1=f1*2;
          }
          else if(t[j]=='?'){
            f1=f1*2+1;
          }
          else{
            f1=f1*2;
            if(!bit(mask,cur)){
              f1++;
            }
            if(bit(mask,cur)){
              c++;
            }
            cur++;
          }
        }
        // cout<<f<<" "<<f1<<"\n";
        int res=dp0[f1];
        if(c%2==1)ans-=res;
        else ans+=res;
      }
      cout<<ans<<"\n";
    }
  }
}

//1010
//0011

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  // cin>>t;
  while(t--)solve();
}

Compilation message

snake_escaping.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
snake_escaping.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 183 ms 12116 KB Output is correct
12 Correct 195 ms 11588 KB Output is correct
13 Correct 325 ms 10968 KB Output is correct
14 Correct 332 ms 11092 KB Output is correct
15 Correct 328 ms 12112 KB Output is correct
16 Correct 467 ms 11420 KB Output is correct
17 Correct 414 ms 11288 KB Output is correct
18 Correct 142 ms 13136 KB Output is correct
19 Correct 189 ms 10068 KB Output is correct
20 Correct 216 ms 11600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 183 ms 12116 KB Output is correct
12 Correct 195 ms 11588 KB Output is correct
13 Correct 325 ms 10968 KB Output is correct
14 Correct 332 ms 11092 KB Output is correct
15 Correct 328 ms 12112 KB Output is correct
16 Correct 467 ms 11420 KB Output is correct
17 Correct 414 ms 11288 KB Output is correct
18 Correct 142 ms 13136 KB Output is correct
19 Correct 189 ms 10068 KB Output is correct
20 Correct 216 ms 11600 KB Output is correct
21 Correct 258 ms 13652 KB Output is correct
22 Correct 256 ms 13652 KB Output is correct
23 Correct 555 ms 12756 KB Output is correct
24 Correct 594 ms 12504 KB Output is correct
25 Correct 413 ms 14724 KB Output is correct
26 Correct 800 ms 13520 KB Output is correct
27 Correct 634 ms 13140 KB Output is correct
28 Correct 150 ms 15552 KB Output is correct
29 Correct 236 ms 11600 KB Output is correct
30 Correct 261 ms 13652 KB Output is correct
31 Correct 662 ms 13532 KB Output is correct
32 Correct 1454 ms 13724 KB Output is correct
33 Correct 370 ms 12584 KB Output is correct
34 Correct 672 ms 12600 KB Output is correct
35 Correct 675 ms 13120 KB Output is correct
36 Correct 182 ms 11608 KB Output is correct
37 Correct 231 ms 13708 KB Output is correct
38 Correct 232 ms 11544 KB Output is correct
39 Correct 568 ms 12860 KB Output is correct
40 Correct 602 ms 12648 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 69 ms 13708 KB Output is correct
12 Correct 56 ms 13556 KB Output is correct
13 Correct 92 ms 13380 KB Output is correct
14 Correct 345 ms 13380 KB Output is correct
15 Correct 75 ms 13476 KB Output is correct
16 Correct 194 ms 13316 KB Output is correct
17 Correct 153 ms 13324 KB Output is correct
18 Correct 47 ms 13564 KB Output is correct
19 Correct 61 ms 13372 KB Output is correct
20 Correct 60 ms 13468 KB Output is correct
21 Correct 136 ms 13552 KB Output is correct
22 Correct 293 ms 13300 KB Output is correct
23 Correct 75 ms 13312 KB Output is correct
24 Correct 186 ms 13388 KB Output is correct
25 Correct 151 ms 13368 KB Output is correct
26 Correct 56 ms 13200 KB Output is correct
27 Correct 58 ms 13392 KB Output is correct
28 Correct 54 ms 13264 KB Output is correct
29 Correct 91 ms 13396 KB Output is correct
30 Correct 143 ms 13308 KB Output is correct
31 Correct 74 ms 13276 KB Output is correct
32 Correct 224 ms 13368 KB Output is correct
33 Correct 144 ms 13492 KB Output is correct
34 Correct 48 ms 13336 KB Output is correct
35 Correct 127 ms 13508 KB Output is correct
36 Correct 115 ms 13488 KB Output is correct
37 Correct 121 ms 13300 KB Output is correct
38 Correct 145 ms 13560 KB Output is correct
39 Correct 114 ms 13360 KB Output is correct
40 Correct 115 ms 13384 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2516 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2524 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 183 ms 12116 KB Output is correct
12 Correct 195 ms 11588 KB Output is correct
13 Correct 325 ms 10968 KB Output is correct
14 Correct 332 ms 11092 KB Output is correct
15 Correct 328 ms 12112 KB Output is correct
16 Correct 467 ms 11420 KB Output is correct
17 Correct 414 ms 11288 KB Output is correct
18 Correct 142 ms 13136 KB Output is correct
19 Correct 189 ms 10068 KB Output is correct
20 Correct 216 ms 11600 KB Output is correct
21 Correct 258 ms 13652 KB Output is correct
22 Correct 256 ms 13652 KB Output is correct
23 Correct 555 ms 12756 KB Output is correct
24 Correct 594 ms 12504 KB Output is correct
25 Correct 413 ms 14724 KB Output is correct
26 Correct 800 ms 13520 KB Output is correct
27 Correct 634 ms 13140 KB Output is correct
28 Correct 150 ms 15552 KB Output is correct
29 Correct 236 ms 11600 KB Output is correct
30 Correct 261 ms 13652 KB Output is correct
31 Correct 662 ms 13532 KB Output is correct
32 Correct 1454 ms 13724 KB Output is correct
33 Correct 370 ms 12584 KB Output is correct
34 Correct 672 ms 12600 KB Output is correct
35 Correct 675 ms 13120 KB Output is correct
36 Correct 182 ms 11608 KB Output is correct
37 Correct 231 ms 13708 KB Output is correct
38 Correct 232 ms 11544 KB Output is correct
39 Correct 568 ms 12860 KB Output is correct
40 Correct 602 ms 12648 KB Output is correct
41 Correct 69 ms 13708 KB Output is correct
42 Correct 56 ms 13556 KB Output is correct
43 Correct 92 ms 13380 KB Output is correct
44 Correct 345 ms 13380 KB Output is correct
45 Correct 75 ms 13476 KB Output is correct
46 Correct 194 ms 13316 KB Output is correct
47 Correct 153 ms 13324 KB Output is correct
48 Correct 47 ms 13564 KB Output is correct
49 Correct 61 ms 13372 KB Output is correct
50 Correct 60 ms 13468 KB Output is correct
51 Correct 136 ms 13552 KB Output is correct
52 Correct 293 ms 13300 KB Output is correct
53 Correct 75 ms 13312 KB Output is correct
54 Correct 186 ms 13388 KB Output is correct
55 Correct 151 ms 13368 KB Output is correct
56 Correct 56 ms 13200 KB Output is correct
57 Correct 58 ms 13392 KB Output is correct
58 Correct 54 ms 13264 KB Output is correct
59 Correct 91 ms 13396 KB Output is correct
60 Correct 143 ms 13308 KB Output is correct
61 Correct 74 ms 13276 KB Output is correct
62 Correct 224 ms 13368 KB Output is correct
63 Correct 144 ms 13492 KB Output is correct
64 Correct 48 ms 13336 KB Output is correct
65 Correct 127 ms 13508 KB Output is correct
66 Correct 115 ms 13488 KB Output is correct
67 Correct 121 ms 13300 KB Output is correct
68 Correct 145 ms 13560 KB Output is correct
69 Correct 114 ms 13360 KB Output is correct
70 Correct 115 ms 13384 KB Output is correct
71 Correct 491 ms 27832 KB Output is correct
72 Correct 426 ms 28148 KB Output is correct
73 Correct 1197 ms 26712 KB Output is correct
74 Execution timed out 2057 ms 18052 KB Time limit exceeded
75 Halted 0 ms 0 KB -