oj.uz

Submission #966298

# Submission time Handle Problem Language Result Execution time Memory
966298 2024-04-19T16:27:13 Z 8pete8 Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 2000 ms 30984 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&&0){//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()&&0){
			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&&0){//5 tl
      |      ~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 385 ms 10412 KB Output is correct
12 Correct 537 ms 10496 KB Output is correct
13 Correct 501 ms 9300 KB Output is correct
14 Correct 505 ms 9580 KB Output is correct
15 Correct 417 ms 10580 KB Output is correct
16 Correct 492 ms 9656 KB Output is correct
17 Correct 522 ms 9556 KB Output is correct
18 Correct 246 ms 11624 KB Output is correct
19 Correct 457 ms 8428 KB Output is correct
20 Correct 398 ms 10092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 385 ms 10412 KB Output is correct
12 Correct 537 ms 10496 KB Output is correct
13 Correct 501 ms 9300 KB Output is correct
14 Correct 505 ms 9580 KB Output is correct
15 Correct 417 ms 10580 KB Output is correct
16 Correct 492 ms 9656 KB Output is correct
17 Correct 522 ms 9556 KB Output is correct
18 Correct 246 ms 11624 KB Output is correct
19 Correct 457 ms 8428 KB Output is correct
20 Correct 398 ms 10092 KB Output is correct
21 Correct 435 ms 10728 KB Output is correct
22 Correct 923 ms 10716 KB Output is correct
23 Correct 683 ms 9876 KB Output is correct
24 Correct 601 ms 9852 KB Output is correct
25 Correct 467 ms 11600 KB Output is correct
26 Correct 590 ms 10064 KB Output is correct
27 Correct 671 ms 10068 KB Output is correct
28 Correct 262 ms 12544 KB Output is correct
29 Correct 631 ms 8636 KB Output is correct
30 Correct 492 ms 11004 KB Output is correct
31 Correct 567 ms 10472 KB Output is correct
32 Correct 571 ms 10580 KB Output is correct
33 Correct 547 ms 9560 KB Output is correct
34 Correct 647 ms 9472 KB Output is correct
35 Correct 669 ms 10068 KB Output is correct
36 Correct 277 ms 8532 KB Output is correct
37 Correct 714 ms 10620 KB Output is correct
38 Correct 958 ms 8876 KB Output is correct
39 Correct 621 ms 9636 KB Output is correct
40 Correct 581 ms 9612 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 126 ms 28676 KB Output is correct
12 Correct 649 ms 28732 KB Output is correct
13 Correct 362 ms 30636 KB Output is correct
14 Correct 144 ms 30708 KB Output is correct
15 Correct 121 ms 30968 KB Output is correct
16 Correct 141 ms 30804 KB Output is correct
17 Correct 181 ms 30644 KB Output is correct
18 Correct 112 ms 30968 KB Output is correct
19 Correct 284 ms 30572 KB Output is correct
20 Correct 118 ms 30724 KB Output is correct
21 Correct 133 ms 30716 KB Output is correct
22 Correct 135 ms 30708 KB Output is correct
23 Correct 121 ms 30708 KB Output is correct
24 Correct 209 ms 30632 KB Output is correct
25 Correct 187 ms 30816 KB Output is correct
26 Correct 106 ms 30712 KB Output is correct
27 Correct 314 ms 30760 KB Output is correct
28 Correct 584 ms 30556 KB Output is correct
29 Correct 140 ms 30724 KB Output is correct
30 Correct 144 ms 30712 KB Output is correct
31 Correct 1356 ms 30788 KB Output is correct
32 Correct 203 ms 30984 KB Output is correct
33 Correct 177 ms 30656 KB Output is correct
34 Execution timed out 2041 ms 29684 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 385 ms 10412 KB Output is correct
12 Correct 537 ms 10496 KB Output is correct
13 Correct 501 ms 9300 KB Output is correct
14 Correct 505 ms 9580 KB Output is correct
15 Correct 417 ms 10580 KB Output is correct
16 Correct 492 ms 9656 KB Output is correct
17 Correct 522 ms 9556 KB Output is correct
18 Correct 246 ms 11624 KB Output is correct
19 Correct 457 ms 8428 KB Output is correct
20 Correct 398 ms 10092 KB Output is correct
21 Correct 435 ms 10728 KB Output is correct
22 Correct 923 ms 10716 KB Output is correct
23 Correct 683 ms 9876 KB Output is correct
24 Correct 601 ms 9852 KB Output is correct
25 Correct 467 ms 11600 KB Output is correct
26 Correct 590 ms 10064 KB Output is correct
27 Correct 671 ms 10068 KB Output is correct
28 Correct 262 ms 12544 KB Output is correct
29 Correct 631 ms 8636 KB Output is correct
30 Correct 492 ms 11004 KB Output is correct
31 Correct 567 ms 10472 KB Output is correct
32 Correct 571 ms 10580 KB Output is correct
33 Correct 547 ms 9560 KB Output is correct
34 Correct 647 ms 9472 KB Output is correct
35 Correct 669 ms 10068 KB Output is correct
36 Correct 277 ms 8532 KB Output is correct
37 Correct 714 ms 10620 KB Output is correct
38 Correct 958 ms 8876 KB Output is correct
39 Correct 621 ms 9636 KB Output is correct
40 Correct 581 ms 9612 KB Output is correct
41 Correct 126 ms 28676 KB Output is correct
42 Correct 649 ms 28732 KB Output is correct
43 Correct 362 ms 30636 KB Output is correct
44 Correct 144 ms 30708 KB Output is correct
45 Correct 121 ms 30968 KB Output is correct
46 Correct 141 ms 30804 KB Output is correct
47 Correct 181 ms 30644 KB Output is correct
48 Correct 112 ms 30968 KB Output is correct
49 Correct 284 ms 30572 KB Output is correct
50 Correct 118 ms 30724 KB Output is correct
51 Correct 133 ms 30716 KB Output is correct
52 Correct 135 ms 30708 KB Output is correct
53 Correct 121 ms 30708 KB Output is correct
54 Correct 209 ms 30632 KB Output is correct
55 Correct 187 ms 30816 KB Output is correct
56 Correct 106 ms 30712 KB Output is correct
57 Correct 314 ms 30760 KB Output is correct
58 Correct 584 ms 30556 KB Output is correct
59 Correct 140 ms 30724 KB Output is correct
60 Correct 144 ms 30712 KB Output is correct
61 Correct 1356 ms 30788 KB Output is correct
62 Correct 203 ms 30984 KB Output is correct
63 Correct 177 ms 30656 KB Output is correct
64 Execution timed out 2041 ms 29684 KB Time limit exceeded
65 Halted 0 ms 0 KB -