#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 1050000;
int m, n1, n2, a[MAXN], b[MAXN];
char buf[22];
int getMask(){
scanf("%s",buf);
int ans = 0;
for(int i=0; buf[i]; i++){
if(buf[i] != '.') ans |= (1<<i);
}
return ans;
}
int dp[MAXN];
int func[MAXN], clos[MAXN], cnt[MAXN], ret[MAXN];
using base = int;
void fft(vector<base> &a, bool inv){
int n = a.size(), j = 0;
for(int i=1; i<n; i++){
int bit = (n >> 1);
while(j >= bit){
j -= bit;
bit >>= 1;
}
j += bit;
if(i < j) swap(a[i], a[j]);
}
for(int i=2; i<=n; i<<=1){
// int step = n / i;
for(int j=0; j<n; j+=i){
for(int k=0; k<i/2; k++){
base u = a[j+k], v = a[j+k+i/2];
a[j+k] = u;
if(!inv) a[j+k+i/2] = u+v;
else a[j+k+i/2] = v -u;
}
}
}
}
void convolute(){
vector<int> ans;
for(int i=0; i<(1<<m); i++){
ans.push_back(clos[i]);
}
fft(ans, 0);
for(int i=0; i<(1<<m); i++) ans[i] *= ans[i];
fft(ans, 1);
for(int i=0; i<(1<<m); i++) clos[i] = ans[i];
}
void make_or_closure(){
for(int i=0; i<5; i++){
convolute();
for(int j=0; j<(1<<m); j++) clos[j] = min(clos[j], 1);
}
}
int main(){
scanf("%d",&m);
scanf("%d",&n1);
for(int i=0; i<n1; i++){
a[i] = getMask();
clos[a[i]] = 1;
}
clos[0] = 1;
make_or_closure();
scanf("%d",&n2);
for(int i=0; i<n2; i++){
b[getMask()] = 1;
// cnt[b[i]]++;
}
// first, count b_i such that, j & b_i neq 0;
/*
for(int i=0; i<m; i++){
for(int j=0; j<(1<<m); j++){
if((j >> i) & 1){
cnt[j] += cnt[j ^ (1<<i)];
}
}
}
*/
for(int i=0; i<(1<<m); i++){
cnt[i] = b[0];
for(int j=i; j; j=(j-1)&i){
cnt[i] += b[j];
}
}
for(int j=0; j<(1<<m); j++){
func[j] = n2 - cnt[((1<<m) - 1) ^ j];
if(clos[j]) ret[func[j]] = 1;
}
for(int i=1; i<=n2; i++) putchar(ret[i] ? 'o' : 'x');
puts("");
}
/*
struct rmq{
int tree[530000], lim;
void init(int n){
memset(tree, 0x3f, sizeof(tree));
for(lim = 1; lim < n; lim <<= 1);
for(int i=0; i<lim; i++){
l[i + lim] = i + 1;
r[i + lim] = i + 1;
}
for(int i=lim-1; i; i--){
l[i] = l[2*i];
r[i] = r[2*i+1];
}
}
int query(int s, int e){
s--, e--;
s += lim;
e += lim;
int ret = 1e9;
while(s < e){
if(s%2 == 1) ret = min(ret, tree[s++]);
if(e%2 == 0) ret = min(ret, tree[e--]);
s >>= 1;
e >>= 1;
}
if(s == e) ret = min(ret, tree[s]);
return ret;
}
}rmq;
int n, q, a[200005];
int main(){
scanf("%d %d",&n,&q);
rmq.init(n);
for(int i=1; i<=n; i++){
scanf("%*d",&a[i]);
rmq.add(i, a[i]);
}
while(q--){ int l, r; scanf("%d %d",&l,&r);
printf("%d\n", rmq.query(l, r));
}
}o*/
Compilation message
judge.cpp: In function 'int getMask()':
judge.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",buf);
~~~~~^~~~~~~~~~
judge.cpp: In function 'int main()':
judge.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&m);
~~~~~^~~~~~~~~
judge.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n1);
~~~~~^~~~~~~~~~
judge.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n2);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
540 KB |
Output is correct |
| 4 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 6 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 7 |
Correct |
27 ms |
1168 KB |
Output is correct |
| 8 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 9 |
Correct |
27 ms |
1168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
540 KB |
Output is correct |
| 4 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 6 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 7 |
Correct |
27 ms |
1168 KB |
Output is correct |
| 8 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 9 |
Correct |
27 ms |
1168 KB |
Output is correct |
| 10 |
Incorrect |
67 ms |
1168 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
540 KB |
Output is correct |
| 4 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 5 |
Correct |
29 ms |
1168 KB |
Output is correct |
| 6 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 7 |
Correct |
27 ms |
1168 KB |
Output is correct |
| 8 |
Correct |
26 ms |
1168 KB |
Output is correct |
| 9 |
Correct |
27 ms |
1168 KB |
Output is correct |
| 10 |
Incorrect |
67 ms |
1168 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
