oj.uz

Submission #966301

# Submission time Handle Problem Language Result Execution time Memory
966301 2024-04-19T16:28:42 Z 8pete8 Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1554 ms 63848 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int dp1[Mxn+10],dp0[Mxn+10],cost[Mxn+10],rdp0[Mxn+10];
int32_t main(){
	fastio
	int n,q;cin>>n>>q;
	string a;cin>>a;
	for(int i=0;i<(1LL<<n);i++)cost[i]=dp1[i]=dp0[i]=(a[i]-'0');
	for(int i=0;i<n;i++)for(int j=0;j<(1LL<<n);j++)if(j&(1LL<<i))dp1[j]+=dp1[j^(1LL<<i)];
	for(int i=0;i<n;i++)for(int j=(1LL<<n)-1;j>=0;j--)if(!(j&(1LL<<i)))dp0[j]+=dp0[j+(1LL<<i)];
	int root=sqrt(n);
	root++;
	auto change=[&](int x){
		int k=0;
		for(int i=0;i<n;i++)if(!(x&(1LL<<i)))k+=1LL<<i;
		return k;
	};
	for(int i=0;i<(1LL<<n);i++)rdp0[change(i)]=dp0[i];
	while(q--){
		cin>>a;
		reverse(all(a));
		int x=0,y=0;
		vector<int>o,z,c;
		int bro=0,bro2=0;
		for(int i=0;i<n;i++){
			if(a[i]=='1')x+=(1LL<<i),o.pb(i),y+=(1LL<<i);
			else if(a[i]=='?')c.pb(i),bro+=(1LL<<i),x+=(1LL<<i),bro2+=(1LL<<i);
			else z.pb(i);
		}
		int m=0;
		int ans=0,g;
		if(c.size()<=root){//5 tl
			m=c.size();
			for(int i=0;i<(1LL<<m);i++){
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x-=(1LL<<c[j]);
				ans+=cost[x];
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x+=(1LL<<c[j]);
			}
		}
		else if(o.size()<z.size()){
			m=o.size();
			x-=bro;
			g=x;
			while(1){
				if((m-__builtin_popcount(g))%2)ans-=dp1[g+bro];
				else ans+=dp1[g+bro];
				if(g==0)break;
				g=(g-1)&x;
			}
			/*
			for(int i=0;i<(1LL<<m)-1;i++){
				int cnt=0;
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x-=(1LL<<o[j]),cnt++;
				if(cnt%2)ans-=dp1[x];
				else ans+=dp1[x];
				for(int j=0;j<m;j++)if((i&(1LL<<j))==0)x+=(1LL<<o[j]);
			}*/
		}
		else{
			m=z.size();
			y=change(y);
			y-=bro2;
			int g=y;
			//cout<<bro2<<' '<<g<<"L\n";
			while(1){
				if((m-__builtin_popcount(g))%2)ans-=rdp0[g+bro2];
				else ans+=rdp0[g+bro2];
				if(g==0)break;
				g=(g-1)&y;
			}
			/*
			ans=dp0[y];
			
			for(int i=1;i<(1LL<<m);i++){
				int cnt=0;
				for(int j=0;j<m;j++)if((i&(1LL<<j)))y+=(1LL<<z[j]),cnt++;
				if(cnt%2)ans-=dp0[y];
				else ans+=dp0[y];
				for(int j=0;j<m;j++)if((i&(1LL<<j)))y-=(1LL<<z[j]);
			}*/
		}
		//ans=abs(ans);
		cout<<ans<<'\n';
		//return 0;
		//cout<<dp1[x]<<" "<<dp0[y]<<'\n';
	}
}
/*
if cnt? <= sqrt(m) we can do (2^4)? bruteforce (maybe even 5)
else we can do sos dp and somehow remove the overcount
we can turn all ? into one and get sos of that bit
overcount when "1" bit that is originaly turned on switch to 0(for subset)
we can switch them off and subtract from the original answer so it cost 2^(cnt1){
	we need to somehow do pie
	starting from original answer-> if we turn off 1 bit
	ans-(turn of x bit)-(turn of y bit)+(turn of x and y bit)
	so if cnt%2==1 then we subtract
	else we add back in
}
cnt1 can be at most 16,worst case is all 1 (2^16)
we can also do sos dp where 0 is now the "switchable" value
so if cnt0<cnt1 we take do from 0 dp else from 1
tc-> worst case q*(2^m)*m
pre com time is m*(2^m+1)
q*(x*(2^x)+(2^(m-x)/2))
*/

Compilation message

snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:68:14: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   68 |   if(c.size()<=root){//5 tl
      |      ~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 386 ms 10504 KB Output is correct
12 Correct 414 ms 10400 KB Output is correct
13 Correct 447 ms 9428 KB Output is correct
14 Correct 452 ms 9460 KB Output is correct
15 Correct 383 ms 10824 KB Output is correct
16 Correct 475 ms 9740 KB Output is correct
17 Correct 480 ms 9556 KB Output is correct
18 Correct 286 ms 11616 KB Output is correct
19 Correct 347 ms 8436 KB Output is correct
20 Correct 402 ms 10276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 386 ms 10504 KB Output is correct
12 Correct 414 ms 10400 KB Output is correct
13 Correct 447 ms 9428 KB Output is correct
14 Correct 452 ms 9460 KB Output is correct
15 Correct 383 ms 10824 KB Output is correct
16 Correct 475 ms 9740 KB Output is correct
17 Correct 480 ms 9556 KB Output is correct
18 Correct 286 ms 11616 KB Output is correct
19 Correct 347 ms 8436 KB Output is correct
20 Correct 402 ms 10276 KB Output is correct
21 Correct 420 ms 10476 KB Output is correct
22 Correct 432 ms 10836 KB Output is correct
23 Correct 526 ms 9816 KB Output is correct
24 Correct 598 ms 9528 KB Output is correct
25 Correct 442 ms 11604 KB Output is correct
26 Correct 556 ms 10196 KB Output is correct
27 Correct 589 ms 9908 KB Output is correct
28 Correct 274 ms 12532 KB Output is correct
29 Correct 381 ms 8664 KB Output is correct
30 Correct 464 ms 10832 KB Output is correct
31 Correct 498 ms 10656 KB Output is correct
32 Correct 553 ms 10620 KB Output is correct
33 Correct 499 ms 9748 KB Output is correct
34 Correct 608 ms 9496 KB Output is correct
35 Correct 557 ms 10108 KB Output is correct
36 Correct 258 ms 8644 KB Output is correct
37 Correct 390 ms 10712 KB Output is correct
38 Correct 410 ms 8656 KB Output is correct
39 Correct 573 ms 9872 KB Output is correct
40 Correct 608 ms 9660 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 121 ms 34552 KB Output is correct
12 Correct 119 ms 34804 KB Output is correct
13 Correct 126 ms 34540 KB Output is correct
14 Correct 131 ms 34544 KB Output is correct
15 Correct 124 ms 34544 KB Output is correct
16 Correct 183 ms 34548 KB Output is correct
17 Correct 151 ms 34544 KB Output is correct
18 Correct 99 ms 34800 KB Output is correct
19 Correct 120 ms 34724 KB Output is correct
20 Correct 123 ms 34544 KB Output is correct
21 Correct 122 ms 34496 KB Output is correct
22 Correct 146 ms 34480 KB Output is correct
23 Correct 128 ms 34544 KB Output is correct
24 Correct 150 ms 34540 KB Output is correct
25 Correct 151 ms 34540 KB Output is correct
26 Correct 100 ms 34544 KB Output is correct
27 Correct 114 ms 34544 KB Output is correct
28 Correct 120 ms 34540 KB Output is correct
29 Correct 130 ms 34540 KB Output is correct
30 Correct 156 ms 34540 KB Output is correct
31 Correct 122 ms 34544 KB Output is correct
32 Correct 158 ms 34556 KB Output is correct
33 Correct 173 ms 34564 KB Output is correct
34 Correct 104 ms 35568 KB Output is correct
35 Correct 135 ms 37596 KB Output is correct
36 Correct 136 ms 36512 KB Output is correct
37 Correct 143 ms 36596 KB Output is correct
38 Correct 151 ms 36572 KB Output is correct
39 Correct 134 ms 36588 KB Output is correct
40 Correct 136 ms 36512 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 386 ms 10504 KB Output is correct
12 Correct 414 ms 10400 KB Output is correct
13 Correct 447 ms 9428 KB Output is correct
14 Correct 452 ms 9460 KB Output is correct
15 Correct 383 ms 10824 KB Output is correct
16 Correct 475 ms 9740 KB Output is correct
17 Correct 480 ms 9556 KB Output is correct
18 Correct 286 ms 11616 KB Output is correct
19 Correct 347 ms 8436 KB Output is correct
20 Correct 402 ms 10276 KB Output is correct
21 Correct 420 ms 10476 KB Output is correct
22 Correct 432 ms 10836 KB Output is correct
23 Correct 526 ms 9816 KB Output is correct
24 Correct 598 ms 9528 KB Output is correct
25 Correct 442 ms 11604 KB Output is correct
26 Correct 556 ms 10196 KB Output is correct
27 Correct 589 ms 9908 KB Output is correct
28 Correct 274 ms 12532 KB Output is correct
29 Correct 381 ms 8664 KB Output is correct
30 Correct 464 ms 10832 KB Output is correct
31 Correct 498 ms 10656 KB Output is correct
32 Correct 553 ms 10620 KB Output is correct
33 Correct 499 ms 9748 KB Output is correct
34 Correct 608 ms 9496 KB Output is correct
35 Correct 557 ms 10108 KB Output is correct
36 Correct 258 ms 8644 KB Output is correct
37 Correct 390 ms 10712 KB Output is correct
38 Correct 410 ms 8656 KB Output is correct
39 Correct 573 ms 9872 KB Output is correct
40 Correct 608 ms 9660 KB Output is correct
41 Correct 121 ms 34552 KB Output is correct
42 Correct 119 ms 34804 KB Output is correct
43 Correct 126 ms 34540 KB Output is correct
44 Correct 131 ms 34544 KB Output is correct
45 Correct 124 ms 34544 KB Output is correct
46 Correct 183 ms 34548 KB Output is correct
47 Correct 151 ms 34544 KB Output is correct
48 Correct 99 ms 34800 KB Output is correct
49 Correct 120 ms 34724 KB Output is correct
50 Correct 123 ms 34544 KB Output is correct
51 Correct 122 ms 34496 KB Output is correct
52 Correct 146 ms 34480 KB Output is correct
53 Correct 128 ms 34544 KB Output is correct
54 Correct 150 ms 34540 KB Output is correct
55 Correct 151 ms 34540 KB Output is correct
56 Correct 100 ms 34544 KB Output is correct
57 Correct 114 ms 34544 KB Output is correct
58 Correct 120 ms 34540 KB Output is correct
59 Correct 130 ms 34540 KB Output is correct
60 Correct 156 ms 34540 KB Output is correct
61 Correct 122 ms 34544 KB Output is correct
62 Correct 158 ms 34556 KB Output is correct
63 Correct 173 ms 34564 KB Output is correct
64 Correct 104 ms 35568 KB Output is correct
65 Correct 135 ms 37596 KB Output is correct
66 Correct 136 ms 36512 KB Output is correct
67 Correct 143 ms 36596 KB Output is correct
68 Correct 151 ms 36572 KB Output is correct
69 Correct 134 ms 36588 KB Output is correct
70 Correct 136 ms 36512 KB Output is correct
71 Correct 705 ms 60068 KB Output is correct
72 Correct 646 ms 60196 KB Output is correct
73 Correct 914 ms 58860 KB Output is correct
74 Correct 985 ms 59316 KB Output is correct
75 Correct 709 ms 61420 KB Output is correct
76 Correct 1363 ms 60460 KB Output is correct
77 Correct 1492 ms 60016 KB Output is correct
78 Correct 443 ms 63848 KB Output is correct
79 Correct 606 ms 57908 KB Output is correct
80 Correct 760 ms 61100 KB Output is correct
81 Correct 919 ms 60864 KB Output is correct
82 Correct 1030 ms 59892 KB Output is correct
83 Correct 826 ms 59192 KB Output is correct
84 Correct 1362 ms 60024 KB Output is correct
85 Correct 1469 ms 59424 KB Output is correct
86 Correct 407 ms 57304 KB Output is correct
87 Correct 616 ms 60396 KB Output is correct
88 Correct 654 ms 57332 KB Output is correct
89 Correct 1054 ms 58968 KB Output is correct
90 Correct 1271 ms 59224 KB Output is correct
91 Correct 790 ms 59316 KB Output is correct
92 Correct 1554 ms 60456 KB Output is correct
93 Correct 1466 ms 60128 KB Output is correct
94 Correct 424 ms 57952 KB Output is correct
95 Correct 1213 ms 60028 KB Output is correct
96 Correct 1173 ms 59856 KB Output is correct
97 Correct 1199 ms 60288 KB Output is correct
98 Correct 1204 ms 60192 KB Output is correct
99 Correct 1249 ms 60020 KB Output is correct
100 Correct 1152 ms 60196 KB Output is correct