oj.uz

답안 #860634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860634 2023-10-13T15:02:53 Z phoenix0423 Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 344 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int sqrtn = 500;
int super[maxn], sub[maxn];
//sos dp + sqrt-sort technique(pigeonhole principle)

int main(void){
	fastio;
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	for(int i = 0; i < (1 << l); i++) sub[i] = super[i] = s[i] - '0';
	for(int i = 0; i < l; i++){
		for(int mask = 0; mask < (1 << l); mask++){
			if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
			else super[mask] += super[mask ^ (1 << i)];
		}
	}
	for(int mask = 0; mask < (1 << l); mask++) cout<<sub[mask]<<" "<<super[mask]<<"\n";
	while(q--){
		string t;
		cin>>t;
		int cnt0 = 0, cnt1 = 0, cnt2 = 0;
		int a = 0, b = 0, c = 0; //a = 0, b = 1, c = 2
		for(int i = 0; i < l; i++){
			char x = t[i];
			if(x == '0') cnt0++, a |= (1 << (l - i - 1));
			else if(x == '1') cnt1++, b |= (1 << (l - i - 1));
			else cnt2++, c |= (1 << (l - i - 1));
		}
		int ans = 0;
		if(cnt2 <= cnt0 && cnt2 <= cnt1){
			for(int mask = c; mask > 0; mask = (mask - 1) & c){
				ans += s[mask | b] - '0';
			}
			ans += s[b] - '0';
		}
		else if(cnt0 <= cnt1){
			for(int mask = a; mask > 0; mask = (mask - 1) & a){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * super[mask | b];
			}
			ans += super[b];
		}
		else{
			for(int mask = b; mask > 0; mask = (mask - 1) & b){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * sub[c | (b ^ mask)];
			}
			ans += sub[c | b];
		}
		cout<<ans<<"\n";
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -