oj.uz

답안 #72049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72049 2018-08-26T04:58:58 Z 마릴린 희정(#2180, gs14004, ho94949) 재채점 전쟁 (FXCUP3_judge) C++17
49 / 100
 1500 ms 92996 KB 
#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()]++;
	//	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++){
		int func = n2 - cnt[((1<<m) - 1) ^ j];
		if(clos[j]) ret[func] = 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);
  ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 31 ms 964 KB Output is correct
5 Correct 31 ms 1040 KB Output is correct
6 Correct 28 ms 1040 KB Output is correct
7 Correct 28 ms 1040 KB Output is correct
8 Correct 29 ms 1096 KB Output is correct
9 Correct 28 ms 1096 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 31 ms 964 KB Output is correct
5 Correct 31 ms 1040 KB Output is correct
6 Correct 28 ms 1040 KB Output is correct
7 Correct 28 ms 1040 KB Output is correct
8 Correct 29 ms 1096 KB Output is correct
9 Correct 28 ms 1096 KB Output is correct
10 Correct 68 ms 1116 KB Output is correct
11 Correct 85 ms 6624 KB Output is correct
12 Correct 15 ms 6624 KB Output is correct
13 Correct 28 ms 6624 KB Output is correct
14 Correct 133 ms 16156 KB Output is correct
15 Correct 141 ms 22544 KB Output is correct
16 Correct 204 ms 40180 KB Output is correct
17 Correct 267 ms 55880 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 31 ms 964 KB Output is correct
5 Correct 31 ms 1040 KB Output is correct
6 Correct 28 ms 1040 KB Output is correct
7 Correct 28 ms 1040 KB Output is correct
8 Correct 29 ms 1096 KB Output is correct
9 Correct 28 ms 1096 KB Output is correct
10 Correct 68 ms 1116 KB Output is correct
11 Correct 85 ms 6624 KB Output is correct
12 Correct 15 ms 6624 KB Output is correct
13 Correct 28 ms 6624 KB Output is correct
14 Correct 133 ms 16156 KB Output is correct
15 Correct 141 ms 22544 KB Output is correct
16 Correct 204 ms 40180 KB Output is correct
17 Correct 267 ms 55880 KB Output is correct
18 Correct 708 ms 68424 KB Output is correct
19 Correct 1495 ms 80404 KB Output is correct
20 Execution timed out 1525 ms 92996 KB Time limit exceeded
21 Halted 0 ms 0 KB -