oj.uz

답안 #72052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72052 2018-08-26T04:59:58 Z 마릴린 희정(#2180, gs14004, ho94949) 재채점 전쟁 (FXCUP3_judge) C++17
100 / 100
 697 ms 63000 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++){
		cnt[getMask()]++;
	}
	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 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 2 ms 376 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 15 ms 864 KB Output is correct
5 Correct 14 ms 916 KB Output is correct
6 Correct 11 ms 916 KB Output is correct
7 Correct 11 ms 916 KB Output is correct
8 Correct 12 ms 916 KB Output is correct
9 Correct 11 ms 956 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 15 ms 864 KB Output is correct
5 Correct 14 ms 916 KB Output is correct
6 Correct 11 ms 916 KB Output is correct
7 Correct 11 ms 916 KB Output is correct
8 Correct 12 ms 916 KB Output is correct
9 Correct 11 ms 956 KB Output is correct
10 Correct 74 ms 1104 KB Output is correct
11 Correct 56 ms 2336 KB Output is correct
12 Correct 20 ms 2336 KB Output is correct
13 Correct 12 ms 2336 KB Output is correct
14 Correct 90 ms 3084 KB Output is correct
15 Correct 100 ms 3084 KB Output is correct
16 Correct 207 ms 3596 KB Output is correct
17 Correct 210 ms 3596 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 15 ms 864 KB Output is correct
5 Correct 14 ms 916 KB Output is correct
6 Correct 11 ms 916 KB Output is correct
7 Correct 11 ms 916 KB Output is correct
8 Correct 12 ms 916 KB Output is correct
9 Correct 11 ms 956 KB Output is correct
10 Correct 74 ms 1104 KB Output is correct
11 Correct 56 ms 2336 KB Output is correct
12 Correct 20 ms 2336 KB Output is correct
13 Correct 12 ms 2336 KB Output is correct
14 Correct 90 ms 3084 KB Output is correct
15 Correct 100 ms 3084 KB Output is correct
16 Correct 207 ms 3596 KB Output is correct
17 Correct 210 ms 3596 KB Output is correct
18 Correct 197 ms 5012 KB Output is correct
19 Correct 258 ms 8932 KB Output is correct
20 Correct 505 ms 13016 KB Output is correct
21 Correct 452 ms 25448 KB Output is correct
22 Correct 630 ms 42540 KB Output is correct
23 Correct 697 ms 63000 KB Output is correct