답안 #72188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72188 2018-08-26T05:51:15 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) 재채점 전쟁 (FXCUP3_judge) C++17
49 / 100
484 ms 191196 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[22], 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 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 6 ms 2868 KB Output is correct
5 Correct 6 ms 2992 KB Output is correct
6 Correct 5 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 2992 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 6 ms 2868 KB Output is correct
5 Correct 6 ms 2992 KB Output is correct
6 Correct 5 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 2992 KB Output is correct
10 Correct 84 ms 2992 KB Output is correct
11 Correct 60 ms 2992 KB Output is correct
12 Correct 14 ms 2992 KB Output is correct
13 Correct 6 ms 3076 KB Output is correct
14 Correct 96 ms 3076 KB Output is correct
15 Correct 146 ms 3720 KB Output is correct
16 Correct 286 ms 3720 KB Output is correct
17 Correct 305 ms 3756 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 6 ms 2868 KB Output is correct
5 Correct 6 ms 2992 KB Output is correct
6 Correct 5 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 6 ms 2992 KB Output is correct
9 Correct 6 ms 2992 KB Output is correct
10 Correct 84 ms 2992 KB Output is correct
11 Correct 60 ms 2992 KB Output is correct
12 Correct 14 ms 2992 KB Output is correct
13 Correct 6 ms 3076 KB Output is correct
14 Correct 96 ms 3076 KB Output is correct
15 Correct 146 ms 3720 KB Output is correct
16 Correct 286 ms 3720 KB Output is correct
17 Correct 305 ms 3756 KB Output is correct
18 Correct 220 ms 23968 KB Output is correct
19 Correct 163 ms 46544 KB Output is correct
20 Runtime error 484 ms 191196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -