This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
#define TASKNAME "snake"
#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 fi first
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define se second
#define pb push_back
#define MASK(i) (1LL << i) //2^i
#define BIT(x, i) (((x) >> (i))&1) //lay bit thu i cua i
using namespace std;
typedef pair<int, int> ii;
/**
Cho n = 2^L - 1 va q truy van:
Voi truy van thu i. Ta duoc 1 chuoi str gom ?, 0, 1:
1 mask goi la khop neu khi ta so tung vi tri thi str[i] bang '?' hoac mask[i] == str[i].
subtask 1: L <= 10, n <= 1000.
subtask 2: L <= 13.
subtask 3: L <= 15
subtask 4: Q <= 50000
subtask 5: L <= 20, Q <= 1000000
Gọi X là số dấu ?
Nếu X <= 10 thì ta bruteforce.
Nếu X > 10 thì ta sẽ có tối đa 9 số. Thì ta sẽ dùng bao hàm bù trừ kết hợp dp SOS để tính nhanh.
**/
const int MAX = MASK(20);
int dp[MAX], val[MAX];
char query[21];
int lengthBit;
int numQuery;
namespace subtask5{
bool check(){
return true;
}
vector<int> hidden;
vector<int> number;
int ans = 0, mask1 = 0, mask2 = 0;
void bruteforce(int pos){
if (pos == hidden.size()){
ans += val[mask1];
return;
}
bruteforce(pos + 1);
mask1 ^= (1LL << hidden[pos]);
bruteforce(pos + 1);
mask1 ^= (1LL << hidden[pos]);
}
void calc2(int pos, int val){
if (pos == number.size()){
ans += dp[mask2] * ((val&1) ? (-1) : (1));
return;
}
calc2(pos + 1, val + 1);
mask2 ^= (1LL << number[pos]);
calc2(pos + 1, val);
mask2 ^= (1LL << number[pos]);
}
void solve(){
FOR(i, 0, numQuery - 1){
mask1 = 0, mask2 = 0, ans = 0;
FORD(j, lengthBit - 1, 0){
cin >> query[j];
if (query[j] == '?') hidden.pb(j), mask2 ^= (1LL << j);
else if (query[j] == '1') number.pb(j), mask1 ^= (1 << j);
}
if (hidden.size() <= 10){
bruteforce(0);
printf("%lld\n", ans);
}
else {
calc2(0, 0);
printf("%lld\n", ans);
}
number.clear();
hidden.clear();
}
}
}
main(){
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> lengthBit >> numQuery;
FOR(i, 0, MASK(lengthBit) - 1){
char c;
cin >> c;
val[i] = (c - '0');
dp[i] += (c - '0');
}
FOR(j, 0, lengthBit - 1){
FOR(i, 0, MASK(lengthBit) - 1){
if (i & (1 << j)) dp[i] += dp[i ^ (1 << j)];
}
}
// FOR(i, 0, MASK(lengthBit) - 1) printf("%lld\n", dp[i]);
if (subtask5::check()) return subtask5::solve(), 0;
}
Compilation message (stderr)
snake_escaping.cpp: In function 'void subtask5::bruteforce(long long int)':
snake_escaping.cpp:45:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (pos == hidden.size()){
| ~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask5::calc2(long long int, long long int)':
snake_escaping.cpp:58:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (pos == number.size()){
| ~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp: At global scope:
snake_escaping.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
90 | main(){
| ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |