Submission #1122183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122183		Mikael639	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1025 ms	27372 KiB

snake_escaping

#include <bits/stdc++.h>

#define fi first
#define se second

#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define coutE(x) {cout << x << '\n'; return;}
#define pb push_back
#define pf push_front

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define bs binary_search
#define ub upper_bound
#define lb lower_bound

#define endl '\n'

#define db long double
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>

#define int long long


using namespace std;

void file(string s){

    if (s.empty()) return;

    freopen((s + ".inp").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

template <class X, class Y>
	bool minimize(X &x, Y y){
		if (x > y){
			x = y;
			return 1;
		}
		
		return 0;
	}

template <class X, class Y>
	bool maximize(X &x, Y y){
		if (x < y){
			x = y;
			return 1;
		}
		
		return 0;
	}


mt19937_64 rng(time(0));

const int N = (1 << 20) + 5;

const int MOD = 1e9 + 7; //998244353;
const int INF = 1e9;
const long long LINF = 1e18;

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

int m, q, a[N], f[N], g[N];
string ss;
vi P[3];

void brute(){
	int M = 0;
	for (int i: P[1]) M |= (1 << i);
	int res = 0;
	rep(msk, 1 << sz(P[2])){
		int tmp = M;
		rep(i, m) if (msk & (1 << i)){
			tmp |= (1 << P[2][i]);
		}
		res += a[tmp];
	}
	cout << res << endl;
}

void solve0(){
	
	int M = 0;
	for (int i: P[1]) M |= (1 << i);
	
	int res = 0;
	rep(msk, 1 << sz(P[0])){
		int tmp = M;
		rep(i, m) if (msk & (1 << i)){
			tmp |= (1 << P[0][i]);
		}
		
		int sgn = __builtin_popcount(msk) & 1 ? -1 : +1;
		res += sgn * g[tmp];
	}
	
	cout << res << endl;
}

void solve1(){
	int M = 0;
	for (int i: P[2]) M |= (1 << i);
	
	int res = 0;
	bool x = sz(P[2]) & 1 ? 1 : 0;
	
	rep(msk, 1 << sz(P[1])){
		int tmp = M;
		rep(i, m) if (msk & (1 << i)){
			tmp |= (1 << P[1][i]);
		}
		
		int sgn = __builtin_popcount(msk) ^ x ? -1 : +1;
		res += sgn * f[tmp];
	}
	
	cout << res << endl;
}

void solve(){

	cin >> m >> q >> ss;
	rep(i, 1 << m)
		a[i] = f[i] = g[i] = ss[i] - '0';
	
	rep(i, m) rep(msk, 1 << m){
		if (msk & (1 << i)){
			f[msk] += f[msk ^ (1 << i)]; 
			g[msk ^ (1 << i)] += g[msk];
		}
	}
	
	while (q--){
		string s; cin >> s;
		reverse(all(s));
		
		rep(i, m){
			if (isdigit(s[i])){
				P[s[i] - '0'].pb(i);
			}
			else P[2].pb(i);
		}
		
		if (sz(P[2]) <= 6) 
			brute();
		else if (sz(P[0]) <= 6) 
			solve0();
		else 
			solve1();
		
		rep(i, 3) P[i].clear();
	}	
}


signed main(){

	ios_base::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0);
	file("");

	int T = 1;
	//cin >> T;
	while (T--) solve();

	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void file(std::string)':
snake_escaping.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25