oj.uz

Submission #966305

# Submission time Handle Problem Language Result Execution time Memory
966305 2024-04-19T16:37:52 Z 8pete8 Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 835 ms 21752 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")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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],cost[Mxn+10],rdp0[Mxn+10];
int32_t main(){
	fastio
	int n,q;cin>>n>>q;
	string a;cin>>a;
	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++)cost[i]=dp1[i]=rdp0[change(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++;
	for(int i=0;i<n;i++)for(int j=0;j<(1LL<<n);j++)if(j&(1LL<<i))rdp0[j]+=rdp0[j^(1LL<<i)];
	while(q--){
		cin>>a;
		reverse(all(a));
		int x=0,y=0;
		vector<int>c;
		int bro=0,bro2=0,c1=0,c0=0;
		for(int i=0;i<n;i++){
			if(a[i]=='1')x+=(1LL<<i),y+=(1LL<<i),c1++;
			else if(a[i]=='?')c.pb(i),bro+=(1LL<<i),x+=(1LL<<i);
			else c0++;
		}
		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(c1<c0){
			m=c1;
			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;
			}
		}
		else{
			m=c0;
			y=change(y);
			y-=bro;
			int g=y;
			while(1){
				if((m-__builtin_popcount(g))%2)ans-=rdp0[g+bro];
				else ans+=rdp0[g+bro];
				if(g==0)break;
				g=(g-1)&y;
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}
/*
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:39:45: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   39 | const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
      |                                             ^~~~
snake_escaping.cpp:39:55: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   39 | const int mod=998244353,mxn=3e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
      |                                                       ^~~~~
snake_escaping.cpp: In function 'int32_t main()':
snake_escaping.cpp:69:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |   if(c.size()<=root){//5 tl
      |      ~~~~~~~~^~~~~~
snake_escaping.cpp:61:13: warning: unused variable 'bro2' [-Wunused-variable]
   61 |   int bro=0,bro2=0,c1=0,c0=0;
      |             ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 290 ms 8364 KB Output is correct
12 Correct 364 ms 8140 KB Output is correct
13 Correct 305 ms 7288 KB Output is correct
14 Correct 348 ms 7396 KB Output is correct
15 Correct 304 ms 8316 KB Output is correct
16 Correct 365 ms 7544 KB Output is correct
17 Correct 382 ms 7636 KB Output is correct
18 Correct 310 ms 9464 KB Output is correct
19 Correct 170 ms 6400 KB Output is correct
20 Correct 345 ms 8120 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 290 ms 8364 KB Output is correct
12 Correct 364 ms 8140 KB Output is correct
13 Correct 305 ms 7288 KB Output is correct
14 Correct 348 ms 7396 KB Output is correct
15 Correct 304 ms 8316 KB Output is correct
16 Correct 365 ms 7544 KB Output is correct
17 Correct 382 ms 7636 KB Output is correct
18 Correct 310 ms 9464 KB Output is correct
19 Correct 170 ms 6400 KB Output is correct
20 Correct 345 ms 8120 KB Output is correct
21 Correct 344 ms 8364 KB Output is correct
22 Correct 352 ms 8660 KB Output is correct
23 Correct 393 ms 7596 KB Output is correct
24 Correct 471 ms 7584 KB Output is correct
25 Correct 345 ms 9556 KB Output is correct
26 Correct 386 ms 8200 KB Output is correct
27 Correct 385 ms 7864 KB Output is correct
28 Correct 300 ms 10568 KB Output is correct
29 Correct 180 ms 6572 KB Output is correct
30 Correct 373 ms 8684 KB Output is correct
31 Correct 382 ms 8376 KB Output is correct
32 Correct 377 ms 8528 KB Output is correct
33 Correct 331 ms 7420 KB Output is correct
34 Correct 430 ms 7564 KB Output is correct
35 Correct 414 ms 7988 KB Output is correct
36 Correct 132 ms 6484 KB Output is correct
37 Correct 293 ms 8584 KB Output is correct
38 Correct 193 ms 6576 KB Output is correct
39 Correct 381 ms 7980 KB Output is correct
40 Correct 424 ms 7372 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 108 ms 14396 KB Output is correct
12 Correct 112 ms 14064 KB Output is correct
13 Correct 139 ms 14064 KB Output is correct
14 Correct 110 ms 14016 KB Output is correct
15 Correct 108 ms 14068 KB Output is correct
16 Correct 115 ms 14064 KB Output is correct
17 Correct 117 ms 14068 KB Output is correct
18 Correct 101 ms 14164 KB Output is correct
19 Correct 105 ms 13912 KB Output is correct
20 Correct 110 ms 14180 KB Output is correct
21 Correct 116 ms 14068 KB Output is correct
22 Correct 119 ms 13920 KB Output is correct
23 Correct 122 ms 14064 KB Output is correct
24 Correct 115 ms 14092 KB Output is correct
25 Correct 139 ms 13976 KB Output is correct
26 Correct 98 ms 13808 KB Output is correct
27 Correct 107 ms 14164 KB Output is correct
28 Correct 101 ms 13820 KB Output is correct
29 Correct 116 ms 13924 KB Output is correct
30 Correct 116 ms 14064 KB Output is correct
31 Correct 106 ms 14072 KB Output is correct
32 Correct 114 ms 14064 KB Output is correct
33 Correct 115 ms 13956 KB Output is correct
34 Correct 104 ms 13964 KB Output is correct
35 Correct 126 ms 13908 KB Output is correct
36 Correct 122 ms 13924 KB Output is correct
37 Correct 142 ms 14068 KB Output is correct
38 Correct 113 ms 14068 KB Output is correct
39 Correct 112 ms 13932 KB Output is correct
40 Correct 108 ms 14068 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 290 ms 8364 KB Output is correct
12 Correct 364 ms 8140 KB Output is correct
13 Correct 305 ms 7288 KB Output is correct
14 Correct 348 ms 7396 KB Output is correct
15 Correct 304 ms 8316 KB Output is correct
16 Correct 365 ms 7544 KB Output is correct
17 Correct 382 ms 7636 KB Output is correct
18 Correct 310 ms 9464 KB Output is correct
19 Correct 170 ms 6400 KB Output is correct
20 Correct 345 ms 8120 KB Output is correct
21 Correct 344 ms 8364 KB Output is correct
22 Correct 352 ms 8660 KB Output is correct
23 Correct 393 ms 7596 KB Output is correct
24 Correct 471 ms 7584 KB Output is correct
25 Correct 345 ms 9556 KB Output is correct
26 Correct 386 ms 8200 KB Output is correct
27 Correct 385 ms 7864 KB Output is correct
28 Correct 300 ms 10568 KB Output is correct
29 Correct 180 ms 6572 KB Output is correct
30 Correct 373 ms 8684 KB Output is correct
31 Correct 382 ms 8376 KB Output is correct
32 Correct 377 ms 8528 KB Output is correct
33 Correct 331 ms 7420 KB Output is correct
34 Correct 430 ms 7564 KB Output is correct
35 Correct 414 ms 7988 KB Output is correct
36 Correct 132 ms 6484 KB Output is correct
37 Correct 293 ms 8584 KB Output is correct
38 Correct 193 ms 6576 KB Output is correct
39 Correct 381 ms 7980 KB Output is correct
40 Correct 424 ms 7372 KB Output is correct
41 Correct 108 ms 14396 KB Output is correct
42 Correct 112 ms 14064 KB Output is correct
43 Correct 139 ms 14064 KB Output is correct
44 Correct 110 ms 14016 KB Output is correct
45 Correct 108 ms 14068 KB Output is correct
46 Correct 115 ms 14064 KB Output is correct
47 Correct 117 ms 14068 KB Output is correct
48 Correct 101 ms 14164 KB Output is correct
49 Correct 105 ms 13912 KB Output is correct
50 Correct 110 ms 14180 KB Output is correct
51 Correct 116 ms 14068 KB Output is correct
52 Correct 119 ms 13920 KB Output is correct
53 Correct 122 ms 14064 KB Output is correct
54 Correct 115 ms 14092 KB Output is correct
55 Correct 139 ms 13976 KB Output is correct
56 Correct 98 ms 13808 KB Output is correct
57 Correct 107 ms 14164 KB Output is correct
58 Correct 101 ms 13820 KB Output is correct
59 Correct 116 ms 13924 KB Output is correct
60 Correct 116 ms 14064 KB Output is correct
61 Correct 106 ms 14072 KB Output is correct
62 Correct 114 ms 14064 KB Output is correct
63 Correct 115 ms 13956 KB Output is correct
64 Correct 104 ms 13964 KB Output is correct
65 Correct 126 ms 13908 KB Output is correct
66 Correct 122 ms 13924 KB Output is correct
67 Correct 142 ms 14068 KB Output is correct
68 Correct 113 ms 14068 KB Output is correct
69 Correct 112 ms 13932 KB Output is correct
70 Correct 108 ms 14068 KB Output is correct
71 Correct 575 ms 18952 KB Output is correct
72 Correct 507 ms 19352 KB Output is correct
73 Correct 646 ms 17908 KB Output is correct
74 Correct 605 ms 17904 KB Output is correct
75 Correct 512 ms 19956 KB Output is correct
76 Correct 750 ms 18196 KB Output is correct
77 Correct 835 ms 17976 KB Output is correct
78 Correct 419 ms 21752 KB Output is correct
79 Correct 361 ms 15952 KB Output is correct
80 Correct 598 ms 18872 KB Output is correct
81 Correct 592 ms 18932 KB Output is correct
82 Correct 658 ms 17908 KB Output is correct
83 Correct 587 ms 17116 KB Output is correct
84 Correct 680 ms 17960 KB Output is correct
85 Correct 747 ms 18456 KB Output is correct
86 Correct 254 ms 15876 KB Output is correct
87 Correct 464 ms 18932 KB Output is correct
88 Correct 328 ms 15860 KB Output is correct
89 Correct 671 ms 17480 KB Output is correct
90 Correct 748 ms 17896 KB Output is correct
91 Correct 557 ms 16976 KB Output is correct
92 Correct 759 ms 18340 KB Output is correct
93 Correct 809 ms 18248 KB Output is correct
94 Correct 223 ms 15860 KB Output is correct
95 Correct 617 ms 17920 KB Output is correct
96 Correct 615 ms 17904 KB Output is correct
97 Correct 631 ms 18032 KB Output is correct
98 Correct 629 ms 18012 KB Output is correct
99 Correct 623 ms 17908 KB Output is correct
100 Correct 697 ms 17936 KB Output is correct