Submission #72044

#	Time	Username	Problem	Language	Result	Execution time	Memory
72044		마릴린 희정 (#118)	Judge Against Wrong Code (FXCUP3_judge)	C++17	10 / 100	59 ms	1168 KiB

judge

#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=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++) 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 (stderr)

judge.cpp: In function 'void fft(std::vector<int>&, bool)':
judge.cpp:25:20: warning: unused variable 'j' [-Wunused-variable]
  int n = a.size(), j = 0;
                    ^
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:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
judge.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n1);
  ~~~~~^~~~~~~~~~
judge.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n2);
  ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 39
• Subtask 3: 0 / 51