oj.uz

Submission #966297

# Submission time Handle Problem Language Result Execution time Memory
966297 2024-04-19T16:24:47 Z 8pete8 Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 633 ms 30728 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((__builtin_popcount(g))%2)ans+=rdp0[g+bro2];
				else ans-=rdp0[g+bro2];
				//cout<<g+bro2<<" "<<rdp0[g+bro2]<<' '<<change(g+bro2)<<" "<<dp0[change(g+bro2)]<<'\n';
				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 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6628 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 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 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6628 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 375 ms 21088 KB Output is correct
12 Correct 399 ms 20612 KB Output is correct
13 Correct 452 ms 19932 KB Output is correct
14 Correct 475 ms 20092 KB Output is correct
15 Correct 375 ms 21040 KB Output is correct
16 Correct 493 ms 20076 KB Output is correct
17 Correct 497 ms 20172 KB Output is correct
18 Correct 257 ms 22100 KB Output is correct
19 Correct 360 ms 19024 KB Output is correct
20 Correct 420 ms 20804 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6628 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 375 ms 21088 KB Output is correct
12 Correct 399 ms 20612 KB Output is correct
13 Correct 452 ms 19932 KB Output is correct
14 Correct 475 ms 20092 KB Output is correct
15 Correct 375 ms 21040 KB Output is correct
16 Correct 493 ms 20076 KB Output is correct
17 Correct 497 ms 20172 KB Output is correct
18 Correct 257 ms 22100 KB Output is correct
19 Correct 360 ms 19024 KB Output is correct
20 Correct 420 ms 20804 KB Output is correct
21 Correct 412 ms 23892 KB Output is correct
22 Correct 422 ms 24148 KB Output is correct
23 Correct 549 ms 22980 KB Output is correct
24 Correct 633 ms 22864 KB Output is correct
25 Correct 437 ms 24904 KB Output is correct
26 Correct 561 ms 23296 KB Output is correct
27 Correct 575 ms 23684 KB Output is correct
28 Correct 281 ms 25940 KB Output is correct
29 Correct 390 ms 21840 KB Output is correct
30 Correct 465 ms 24092 KB Output is correct
31 Correct 502 ms 24148 KB Output is correct
32 Correct 552 ms 23888 KB Output is correct
33 Correct 488 ms 22868 KB Output is correct
34 Correct 609 ms 22920 KB Output is correct
35 Correct 575 ms 23448 KB Output is correct
36 Correct 268 ms 22072 KB Output is correct
37 Correct 386 ms 23824 KB Output is correct
38 Correct 404 ms 21844 KB Output is correct
39 Correct 566 ms 23140 KB Output is correct
40 Correct 612 ms 23052 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6628 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 122 ms 30704 KB Output is correct
12 Incorrect 117 ms 30728 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6628 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 375 ms 21088 KB Output is correct
12 Correct 399 ms 20612 KB Output is correct
13 Correct 452 ms 19932 KB Output is correct
14 Correct 475 ms 20092 KB Output is correct
15 Correct 375 ms 21040 KB Output is correct
16 Correct 493 ms 20076 KB Output is correct
17 Correct 497 ms 20172 KB Output is correct
18 Correct 257 ms 22100 KB Output is correct
19 Correct 360 ms 19024 KB Output is correct
20 Correct 420 ms 20804 KB Output is correct
21 Correct 412 ms 23892 KB Output is correct
22 Correct 422 ms 24148 KB Output is correct
23 Correct 549 ms 22980 KB Output is correct
24 Correct 633 ms 22864 KB Output is correct
25 Correct 437 ms 24904 KB Output is correct
26 Correct 561 ms 23296 KB Output is correct
27 Correct 575 ms 23684 KB Output is correct
28 Correct 281 ms 25940 KB Output is correct
29 Correct 390 ms 21840 KB Output is correct
30 Correct 465 ms 24092 KB Output is correct
31 Correct 502 ms 24148 KB Output is correct
32 Correct 552 ms 23888 KB Output is correct
33 Correct 488 ms 22868 KB Output is correct
34 Correct 609 ms 22920 KB Output is correct
35 Correct 575 ms 23448 KB Output is correct
36 Correct 268 ms 22072 KB Output is correct
37 Correct 386 ms 23824 KB Output is correct
38 Correct 404 ms 21844 KB Output is correct
39 Correct 566 ms 23140 KB Output is correct
40 Correct 612 ms 23052 KB Output is correct
41 Correct 122 ms 30704 KB Output is correct
42 Incorrect 117 ms 30728 KB Output isn't correct
43 Halted 0 ms 0 KB -