Submission #72039

#TimeUsernameProblemLanguageResultExecution timeMemory
72039마릴린 희정 (#118)Judge Against Wrong Code (FXCUP3_judge)C++17
10 / 100
59 ms4200 KiB
#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; vector<base> roots(n/2); 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] = u-v; } } } } 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++) ans[i] = clos[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 (stderr)

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:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
judge.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n1);
  ~~~~~^~~~~~~~~~
judge.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n2);
  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...