oj.uz

답안 #72192

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72192 2018-08-26T05:52:38 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) 재채점 전쟁 (FXCUP3_judge) C++17
100 / 100
 596 ms 101832 KB 
#include<cstdio>
#include<algorithm>
using namespace std;
int K, n, m, A[1<<20], B[1<<20], C[21][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);
   ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 7 ms 2892 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 7 ms 2892 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 82 ms 3072 KB Output is correct
11 Correct 63 ms 3072 KB Output is correct
12 Correct 15 ms 3072 KB Output is correct
13 Correct 7 ms 3196 KB Output is correct
14 Correct 113 ms 3324 KB Output is correct
15 Correct 171 ms 3872 KB Output is correct
16 Correct 276 ms 3872 KB Output is correct
17 Correct 298 ms 3884 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 7 ms 2892 KB Output is correct
5 Correct 6 ms 2944 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 82 ms 3072 KB Output is correct
11 Correct 63 ms 3072 KB Output is correct
12 Correct 15 ms 3072 KB Output is correct
13 Correct 7 ms 3196 KB Output is correct
14 Correct 113 ms 3324 KB Output is correct
15 Correct 171 ms 3872 KB Output is correct
16 Correct 276 ms 3872 KB Output is correct
17 Correct 298 ms 3884 KB Output is correct
18 Correct 272 ms 23980 KB Output is correct
19 Correct 166 ms 46652 KB Output is correct
20 Correct 394 ms 100620 KB Output is correct
21 Correct 296 ms 100620 KB Output is correct
22 Correct 527 ms 101832 KB Output is correct
23 Correct 596 ms 101832 KB Output is correct