답안 #72182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72182 2018-08-26T05:48:55 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) 재채점 전쟁 (FXCUP3_judge) C++17
49 / 100
419 ms 191252 KB
#include<cstdio>
#include<algorithm>
using namespace std;
int K, n, m, A[1<<20], B[1<<20], C[20][1<<20], CA[1<<20], CB[1<<20], vis[1<<20];
char p[20], q[10] = "xo";
void Calc(int *a) {
	int i, j;
	for (i = 0; i < (1 << K); i++)C[0][i] = a[i];
	for (i = 0; i < K; i++) {
		for (j = 0; j < (1 << K); j++) {
			if ((j >> i) & 1) {
				C[i + 1][j] = C[i][j] + C[i][j ^ (1 << i)];
			}
			else C[i + 1][j] = C[i][j];
		}
	}
}
int main() {
	int i, j;
	scanf("%d%d", &K, &n);
	for (i = 0; i < n; i++) {
		scanf("%s", p);
		int s = 0;
		for (j = 0; j < K; j++) {
			if (p[j] == 'o')s += (1 << j);
		}
		A[s]++;
	}
	scanf("%d", &m);
	for (i = 0; i < m; i++) {
		scanf("%s", p);
		int s = 0;
		for (j = 0; j < K; j++) {
			if (p[j] == 'x')s += (1 << j);
		}
		B[s]++;
	}
	Calc(A);
	for (i = 0; i < (1 << K); i++)CA[i] = C[K][i];
	Calc(B);
	for (i = 0; i < (1 << K); i++)CB[i] = C[K][i];
	for (i = 1; i < (1 << K); i++) {
		for (j = 0; j < K; j++) {
			if (((i >> j) & 1) && CA[i] == CA[i ^ (1 << j)])break;
		}
		if (j == K) {
			vis[m - CB[(1 << K) - 1 - i]] = 1;
		}
	}
	for (i = 1; i <= m; i++)printf("%c", q[vis[i]]);
	puts("");
	return 0;
}


/*#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 303000
#define M_ 1010000
#define INF 99999999
using namespace std;
int n;
struct Edge {
	int b, e, f;
};
class MaxFlow {
public:
	Edge E[M_ * 2];
	vector<int>G[N_];
	int Level[N_], Q[N_], PV[N_], source, sink, n, flow, EC;
	void init(int N, int S, int T) {
		n = N, flow = EC = 0;
		source = S, sink = T;
		for (int i = 0; i <= N; i++)G[i].clear();
	}
	void Add_Edge(int a, int b, int f) {
		G[a].push_back(EC);
		G[b].push_back(EC + 1);
		E[EC++] = { a,b,f};
		E[EC++] = { b,a,0};
	}
	bool GetLevel() {
		int i;
		for (i = 1; i <= n; i++)Level[i] = -1;
		int head = 0, tail = 0;
		Q[++tail] = source, Level[source] = 0;
		while (head < tail) {
			int x = Q[++head];
			for (auto &y : G[x]) {
				if (E[y].f && Level[E[y].e] == -1) {
					Q[++tail] = E[y].e;
					Level[E[y].e] = Level[x] + 1;
				}
			}
		}
		return Level[sink] != -1;
	}
	int BlockFlow(int a, int f) {
		if (a == sink)return f;
		for (int &i = PV[a]; i >= 0; i--) {
			int x = G[a][i];
			if (E[x].f && Level[E[x].e] == Level[a] + 1) {
				int t = BlockFlow(E[x].e, min(f, E[x].f));
				if (t) {
					E[x].f -= t;
					E[x ^ 1].f += t;
					return t;
				}
			}
		}
		return 0;
	}
	void Dinic() {
		int t;
		while (GetLevel()) {
			for (int i = 1; i <= n; i++)PV[i] = G[i].size() - 1;
			while (t = BlockFlow(source, INF)) flow += t;
		}
	}
}G1;

vector<int>E[N_];

int Col[N_];

void DFS(int a, int pp, int col) {
	Col[a] = col;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a, 3 - col);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int i, a, b;
	scanf("%d", &n);
	G1.init(n + 2, n + 1, n + 2);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1, 0, 1);
	for (i = 1; i <= n; i++) {
		for (auto &x : E[i]) {
			if (Col[i] == 1) G1.Add_Edge(i, x, 1);
		}
		if (Col[i] == 1)G1.Add_Edge(G1.source, i, n - 1 - E[i].size());
		else G1.Add_Edge(i, G1.sink, n - 1 - E[i].size());
	}
	G1.Dinic();
	printf("%d\n", G1.flow);
	for (i = 1; i <= n; i++) {
		if (Col[i] == 1) {
			for (auto &x : G1.G[i]) {
				Edge tp = G1.E[x];
				if (tp.e >= 1 && tp.e <= n && !tp.f) {
				}
			}
		}
	}

}*/

Compilation message

judge.cpp: In function 'int main()':
judge.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &K, &n);
  ~~~~~^~~~~~~~~~~~~~~~
judge.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p);
   ~~~~~^~~~~~~~~
judge.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
judge.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p);
   ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 6 ms 2984 KB Output is correct
6 Correct 7 ms 3116 KB Output is correct
7 Correct 5 ms 3116 KB Output is correct
8 Correct 5 ms 3116 KB Output is correct
9 Correct 6 ms 3116 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 6 ms 2984 KB Output is correct
6 Correct 7 ms 3116 KB Output is correct
7 Correct 5 ms 3116 KB Output is correct
8 Correct 5 ms 3116 KB Output is correct
9 Correct 6 ms 3116 KB Output is correct
10 Correct 88 ms 3116 KB Output is correct
11 Correct 68 ms 3116 KB Output is correct
12 Correct 15 ms 3116 KB Output is correct
13 Correct 6 ms 3212 KB Output is correct
14 Correct 111 ms 3304 KB Output is correct
15 Correct 159 ms 3980 KB Output is correct
16 Correct 259 ms 3980 KB Output is correct
17 Correct 301 ms 3980 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 5 ms 2928 KB Output is correct
5 Correct 6 ms 2984 KB Output is correct
6 Correct 7 ms 3116 KB Output is correct
7 Correct 5 ms 3116 KB Output is correct
8 Correct 5 ms 3116 KB Output is correct
9 Correct 6 ms 3116 KB Output is correct
10 Correct 88 ms 3116 KB Output is correct
11 Correct 68 ms 3116 KB Output is correct
12 Correct 15 ms 3116 KB Output is correct
13 Correct 6 ms 3212 KB Output is correct
14 Correct 111 ms 3304 KB Output is correct
15 Correct 159 ms 3980 KB Output is correct
16 Correct 259 ms 3980 KB Output is correct
17 Correct 301 ms 3980 KB Output is correct
18 Correct 224 ms 23976 KB Output is correct
19 Correct 147 ms 46572 KB Output is correct
20 Runtime error 419 ms 191252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -