CODE FESTIVAL 2016 Final

Submission #3516307

Source codeソースコード

#include <stdio.h>
#include <stdlib.h>

typedef struct graph_edge_sub graph_edge;

typedef struct {
	int num;
	int next_num;
	graph_edge *next;
	int prev_num;
}graph_vertex_sub;

struct graph_edge_sub{
	graph_vertex_sub *v;
	graph_edge *next;
};

typedef struct graph_v_sub graph_vertex;

struct graph_v_sub{
	int num;
	int next_num;
	graph_vertex **next;
	int prev_num;
	graph_vertex **prev;
};

typedef struct {
	int N;
	graph_vertex_sub **v_s;
	graph_vertex **v;
}graph;

//頂点数N, 各頂点の初期値ini_valのグラフを作る
graph *make_graph(int N){
	int i;
	graph *g = (graph *)malloc(sizeof(graph));
	g->N = N;
	g->v_s = (graph_vertex_sub **)malloc(sizeof(graph_vertex_sub *) * N);
	g->v = (graph_vertex **)malloc(sizeof(graph_vertex *) * N);
	for(i = 0; i < N; i++){
		(g->v_s)[i] = (graph_vertex_sub *)malloc(sizeof(graph_vertex_sub));
		(g->v_s)[i]->num = i;
		(g->v_s)[i]->next_num = 0;
		(g->v_s)[i]->next = NULL;
		(g->v_s)[i]->prev_num = 0;
		(g->v)[i] = (graph_vertex *)malloc(sizeof(graph_vertex));
		(g->v)[i]->num = i;
		(g->v)[i]->next_num = 0;
		(g->v)[i]->next = NULL;
		(g->v)[i]->prev_num = 0;
		(g->v)[i]->prev = NULL;
	}
	return g;
}

//グラフgの頂点aから頂点bに重みwの有向辺を張る (0 <= a, b <= N - 1)
void set_edge_graph(int a, int b, graph *g){
	graph_edge *new1 = (graph_edge *)malloc(sizeof(graph_edge));
	new1->v = (g->v_s)[b];
	new1->next = (g->v_s)[a]->next;
	(g->v_s)[a]->next = new1;
	(g->v_s)[a]->next_num++;
	(g->v_s)[b]->prev_num++;
}

//set_edge_graph後に呼び出す
void build_graph(graph *g){
	int i;
	graph_vertex_sub **v_s = g->v_s;
	graph_vertex **v = g->v;
	graph_vertex *nowv;
	graph_edge *nowe;
	for(i = 0; i < g->N; i++){
		v[i]->next = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->next_num);
		v[i]->prev = (graph_vertex **)malloc(sizeof(graph_vertex *) * v_s[i]->prev_num);
	}
	for(i = 0; i < g->N; i++){
		nowv = v[i];
		for(nowe = v_s[i]->next; nowe != NULL; nowe = nowe->next){
			(nowv->next)[nowv->next_num] = v[nowe->v->num];
			nowv->next_num++;
			(v[nowe->v->num]->prev)[v[nowe->v->num]->prev_num] = nowv;
			v[nowe->v->num]->prev_num++;
		}
	}
}

typedef struct SCC_sub{
	int num; //強連結成分番号
	int vertex_num; //強連結成分に含まれる頂点の個数
	int *vertexs; //強連結成分に含まれる元のグラフでの頂点番号
	int next_num;
	struct SCC_sub **next;
	int prev_num;
//	struct SCC_sub **prev;
}SCC; //強連結成分(Strongly Connected Components)

typedef struct {
	int N;
	SCC **sorted_SCC; //topological sort済み
}DAG; //非閉路有向グラフ(Directed Acyclic Graph)

int dfs(int next_bt, int *used, int *bt, int *bt_inv, graph_vertex *v){
	if(used[v->num] == 1){
		return next_bt;
	}
	else{
		int i;
		used[v->num] = 1;
		for(i = 0; i < v->next_num; i++){
			next_bt = dfs(next_bt, used, bt, bt_inv, v->next[i]);
		}
		bt[v->num] = next_bt;
		bt_inv[next_bt] = v->num;
		return next_bt + 1;
	}
}

void dfs_rev1(int next_SCC_num, int *used, int *SCC_num, int *next_num, int *prev_num, graph_vertex *v){
	if(used[v->num] == 1){
		int i;
		used[v->num] = 2;
		for(i = 0; i < v->prev_num; i++){
			dfs_rev1(next_SCC_num, used, SCC_num, next_num, prev_num, v->prev[i]);
		}
		SCC_num[v->num] = next_SCC_num;
		for(i = 0; i < v->next_num; i++){
			if(used[v->next[i]->num] == 1){
				next_num[v->num]++;
				prev_num[v->next[i]->num]++; //ここで自己ループを数えてしまう可能性がある
			}
		}
	}
}

void dfs_rev2(SCC *now_SCC, int *used, int *SCC_num, graph_vertex *v, DAG *dag){
	if(used[v->num] == 2){
		int i;
		SCC *next_SCC;
		used[v->num] = 3;
		for(i = 0; i < v->prev_num; i++){
			dfs_rev2(now_SCC, used, SCC_num, v->prev[i], dag);
		}
		now_SCC->vertexs[now_SCC->vertex_num] = v->num;
		now_SCC->vertex_num++;
		for(i = 0; i < v->next_num; i++){
			if(used[v->next[i]->num] == 2){
				next_SCC = dag->sorted_SCC[SCC_num[v->next[i]->num]];
				if(now_SCC->num != next_SCC->num){ //自己ループがないようにしている
					now_SCC->next[now_SCC->next_num] = next_SCC;
					now_SCC->next_num++;
//					next_SCC->prev[next_SCC->prev_num] = now_SCC;
					next_SCC->prev_num++;
				}
			}
		}
	}
}

DAG *build_DAG(graph *g){
	int N = g->N, i;
	int *used = (int *)malloc(sizeof(int) * N);

	int *bt = (int *)malloc(sizeof(int) * N);
	int *bt_inv = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		used[i] = 0;
		bt[i] = -1;
		bt_inv[i] = -1;
	}
	int next_bt;
	for(i = 0, next_bt = 0; i < N; i++){
		next_bt = dfs(next_bt, used, bt, bt_inv, g->v[i]);
	}

	int *SCC_num = (int *)malloc(sizeof(int) * N);
	int *next_num = (int *)malloc(sizeof(int) * N);
	int *prev_num = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		SCC_num[i] = 0;
		next_num[i] = 0;
		prev_num[i] = 0;
	}
	int next_SCC_num;
	for(i = N - 1, next_SCC_num = 0; i >= 0; i--){
		if(used[bt_inv[i]] == 1){
			dfs_rev1(next_SCC_num, used, SCC_num, next_num, prev_num, g->v[bt_inv[i]]);
			next_SCC_num++;
		}
	}

	DAG *dag = (DAG *)malloc(sizeof(DAG));
	SCC *now_SCC;
	dag->N = next_SCC_num;
	dag->sorted_SCC = (SCC **)malloc(sizeof(SCC *) * dag->N);
	for(i = 0; i < dag->N; i++){
		dag->sorted_SCC[i] = (SCC *)malloc(sizeof(SCC));
		now_SCC = dag->sorted_SCC[i];
		now_SCC->num = i;
		now_SCC->vertex_num = 0;
		now_SCC->vertexs = NULL;
		now_SCC->next_num = 0;
		now_SCC->next = NULL;
		now_SCC->prev_num = 0;
//		now_SCC->prev = NULL;
	}
	for(i = 0; i < N; i++){
		now_SCC = dag->sorted_SCC[SCC_num[i]];
		now_SCC->vertex_num++;
		now_SCC->next_num += next_num[i];
		now_SCC->prev_num += prev_num[i];
	}
	for(i = 0; i < dag->N; i++){
		now_SCC = dag->sorted_SCC[i];
		now_SCC->vertexs = (int *)malloc(sizeof(int) * now_SCC->vertex_num);
		now_SCC->next = (SCC **)malloc(sizeof(SCC *) * now_SCC->next_num);
//		now_SCC->prev = (SCC **)malloc(sizeof(SCC *) * now_SCC->prev_num);
		now_SCC->vertex_num = 0;
		now_SCC->next_num = 0;
		now_SCC->prev_num = 0;
	}

	for(i = N - 1, next_SCC_num = 0; i >= 0; i--){
		if(used[bt_inv[i]] == 2){
			dfs_rev2(dag->sorted_SCC[next_SCC_num], used, SCC_num, g->v[bt_inv[i]], dag);
			next_SCC_num++;
		}
	}
	free(used);
	free(bt);
	free(bt_inv);
	free(SCC_num);
	free(next_num);
	free(prev_num);

	return dag;
}

typedef struct {
	int i;
	int v;
}pair;

typedef struct {
	int x;
	int y;
}pos;

int pos_to_int(int x, int y, int N){
	return N * x + y;
}

pos int_to_pos(int num, int N){
	return (pos){num / N, num % N};
}

//v降順
signed compair(const void *a, const void *b){
	return ((pair *)b)->v - ((pair *)a)->v;
}

int search(int x, int y, int N, int **nexts_num, int ***nexts, int **visited){
	if(visited[x][y] == 2 || visited[x][y] == -1){
		return 0;
	}
	else if(visited[x][y] == 1){
		visited[x][y] = 2;
		return 1;
	}
	else{
		visited[x][y] = 1;
		int i;
		for(i = 0; i < nexts_num[x][y]; i++){
			pos p = int_to_pos(nexts[x][y][i], N);
			if(search(p.x, p.y, N, nexts_num, nexts, visited) == 1){
				if(visited[x][y] == 2){
					return 0;
				}
				else{
					visited[x][y] = 2;
					return 1;
				}
			}
		}
		visited[x][y] = -1;
		return 0;
	}
}

int main(){
	int N, i, j, k;
	scanf("%d", &N);
	int *U = (int *)malloc(sizeof(int) * N);
	int *D = (int *)malloc(sizeof(int) * N);
	int *L = (int *)malloc(sizeof(int) * N);
	int *R = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &U[i]);
	}
	for(i = 0; i < N; i++){
		scanf("%d", &D[i]);
	}
	for(i = 0; i < N; i++){
		scanf("%d", &L[i]);
	}
	for(i = 0; i < N; i++){
		scanf("%d", &R[i]);
	}
	pair *UD = (pair *)malloc(sizeof(pair) * N);
	pair *LR = (pair *)malloc(sizeof(pair) * N);
	for(i = 0; i < N; i++){
		UD[i].i = i;
		UD[i].v = U[i] + D[i];
		LR[i].i = i;
		LR[i].v = N - (L[i] + R[i]);
	}
	qsort(UD, N, sizeof(pair), compair);
	qsort(LR, N, sizeof(pair), compair);
	int **B0 = (int **)malloc(sizeof(int *) * N);
	for(i = 0; i < N; i++){
		B0[i] = (int *)malloc(sizeof(int) * N);
		for(j = 0; j < N; j++){
			B0[i][j] = 0;
		}
	}
	int lastv, l, r, tmp;
	for(i = 0; i < N; i++){
		if(LR[i].v == 0){
			break;
		}
		for(j = 0; j < LR[i].v; j++){
			B0[i][j] = 1;
		}
		lastv = UD[j - 1].v;
		for(l = 0; UD[l].v != lastv; l++);
		for(r = N - 1; UD[r].v != lastv; r--);
		for(k = 0; k <= (r - l) / 2; k++){
			tmp = B0[i][l + k];
			B0[i][l + k] = B0[i][r - k];
			B0[i][r - k] = tmp;
		}
		for(j = 0; j < N; j++){
			UD[j].v -= B0[i][j];
			if(UD[j].v < 0){
				printf("NO\n");
				return 0;
			}
		}
	}
	int **B1 = (int **)malloc(sizeof(int *) * N);
	char **A = (char **)malloc(sizeof(char *) * N);
	int **visited = (int **)malloc(sizeof(int *) * N);
	int **nexts_num = (int **)malloc(sizeof(int *) * N);
	int ***nexts = (int ***)malloc(sizeof(int **) * N);
	for(i = 0; i < N; i++){
		B1[i] = (int *)malloc(sizeof(int) * N);
		A[i] = (char *)malloc(sizeof(char) * N);
		visited[i] = (int *)malloc(sizeof(int) * N);
		nexts_num[i] = (int *)malloc(sizeof(int) * N);
		nexts[i] = (int **)malloc(sizeof(int *) * N);
		for(j = 0; j < N; j++){
			nexts[i][j] = (int *)malloc(sizeof(int) * N);
		}
	}
	for(i = 0; i < N; i++){
		for(j = 0; j < N; j++){
			B1[LR[i].i][UD[j].i] = B0[i][j];
		}
	}
	while(1){
		for(i = 0; i < N; i++){
			for(j = 0, k = 0; k < L[i]; j++){
				if(B1[i][j] == 0){
					A[i][j] = 'L';
					k++;
				}
			}
			for(j = N - 1, k = 0; k < R[i]; j--){
				if(B1[i][j] == 0){
					A[i][j] = 'R';
					k++;
				}
			}
		}
		for(j = 0; j < N; j++){
			for(i = 0, k = 0; k < U[j]; i++){
				if(B1[i][j] == 1){
					A[i][j] = 'U';
					k++;
				}
			}
			for(i = N - 1, k = 0; k < D[j]; i--){
				if(B1[i][j] == 1){
					A[i][j] = 'D';
					k++;
				}
			}
		}
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				nexts_num[i][j] = 0;
			}
		}
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				if(B1[i][j] == 1){
					for(k = j + 1; k < N; k++){
						if(A[i][k] == 'L'){
							nexts[i][j][nexts_num[i][j]] = pos_to_int(i, k, N);
							nexts_num[i][j]++;
						}
					}
				}
			}
			for(j = N - 1; j >= 0; j--){
				if(B1[i][j] == 1){
					for(k = j - 1; k >= 0; k--){
						if(A[i][k] == 'R'){
							nexts[i][j][nexts_num[i][j]] = pos_to_int(i, k, N);
							nexts_num[i][j]++;
						}
					}
				}
			}
		}
		for(j = 0; j < N; j++){
			for(i = 0; i < N; i++){
				if(B1[i][j] == 0){
					for(k = i + 1; k < N; k++){
						if(A[k][j] == 'U'){
							nexts[i][j][nexts_num[i][j]] = pos_to_int(k, j, N);
							nexts_num[i][j]++;
						}
					}
				}
			}
			for(i = N - 1; i >= 0; i--){
				if(B1[i][j] == 0){
					for(k = i - 1; k >= 0; k--){
						if(A[k][j] == 'D'){
							nexts[i][j][nexts_num[i][j]] = pos_to_int(k, j, N);
							nexts_num[i][j]++;
						}
					}
				}
			}
		}
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				visited[i][j] = 0;
			}
		}
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				search(i, j, N, nexts_num, nexts, visited);
			}
		}
		int reverse_num = 0;
		for(i = 0; i < N; i++){
			for(j = 0; j < N; j++){
				if(visited[i][j] == 2){
					B1[i][j] ^= 1;
					reverse_num++;
				}
			}
		}
		if(reverse_num == 0){
			break;
		}
	}
	graph *g = make_graph(N * N);
	for(i = 0; i < N; i++){
		for(j = 0; j < N; j++){
			for(k = j + 1; k < N; k++){
				if(A[i][k] == 'L'){
					set_edge_graph(pos_to_int(i, j, N), pos_to_int(i, k, N), g);
					break;
				}
			}
		}
		for(j = N - 1; j >= 0; j--){
			for(k = j - 1; k >= 0; k--){
				if(A[i][k] == 'R'){
					set_edge_graph(pos_to_int(i, j, N), pos_to_int(i, k, N), g);
					break;
				}
			}
		}
	}
	for(j = 0; j < N; j++){
		for(i = 0; i < N; i++){
			for(k = i + 1; k < N; k++){
				if(A[k][j] == 'U'){
					set_edge_graph(pos_to_int(i, j, N), pos_to_int(k, j, N), g);
					break;
				}
			}
		}
		for(i = N - 1; i >= 0; i--){
			for(k = i - 1; k >= 0; k--){
				if(A[k][j] == 'D'){
					set_edge_graph(pos_to_int(i, j, N), pos_to_int(k, j, N), g);
					break;
				}
			}
		}
	}
	build_graph(g);
	DAG *dag = build_DAG(g);
	for(i = 0; i < dag->N; i++){
		pos p = int_to_pos(dag->sorted_SCC[i]->vertexs[0], N);
		printf("%c", A[p.x][p.y]);
		if(B1[p.x][p.y] == 0){
			printf("%d\n", p.x + 1);
		}
		else{
			printf("%d\n", p.y + 1);
		}
	}
	return 0;
}

Submission

Task問題 J - Neue Spiel
User nameユーザ名 081_abc050
Created time投稿日時
Language言語 C (GCC 5.4.1)
Status状態 AC
Score得点 2100
Source lengthソースコード長 12578 Byte
File nameファイル名
Exec time実行時間 868 ms
Memory usageメモリ使用量 141948 KB

Compiler messageコンパイルメッセージ

./Main.c: In function ‘main’:
./Main.c:293:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.c:299:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &U[i]);
^
./Main.c:302:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &D[i]);
^
./Main.c:305:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &L[i]);
^
./Main.c:308:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &R[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 2000 / 2000 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt
dataset2 100 / 100 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,01-11.txt,01-12.txt,01-13.txt,01-14.txt,01-15.txt,01-16.txt,01-17.txt,01-18.txt,01-19.txt,01-20.txt,01-21.txt,01-22.txt,01-23.txt,01-24.txt,01-25.txt,01-26.txt,01-27.txt,01-28.txt,01-29.txt,01-30.txt,01-31.txt,01-32.txt,01-33.txt,01-34.txt,01-35.txt,01-36.txt,01-37.txt,01-38.txt,01-39.txt,01-40.txt,01-41.txt,01-42.txt,01-43.txt,01-44.txt,01-45.txt,01-46.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 128 KB
01-02.txt AC 1 ms 128 KB
01-03.txt AC 1 ms 128 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 2 ms 640 KB
01-07.txt AC 3 ms 1024 KB
01-08.txt AC 3 ms 1024 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 2 ms 1024 KB
01-11.txt AC 2 ms 1024 KB
01-12.txt AC 2 ms 1024 KB
01-13.txt AC 2 ms 1024 KB
01-14.txt AC 1 ms 128 KB
01-15.txt AC 2 ms 896 KB
01-16.txt AC 2 ms 1024 KB
01-17.txt AC 3 ms 1024 KB
01-18.txt AC 3 ms 1024 KB
01-19.txt AC 1 ms 128 KB
01-20.txt AC 3 ms 1024 KB
01-21.txt AC 3 ms 1024 KB
01-22.txt AC 1 ms 128 KB
01-23.txt AC 1 ms 128 KB
01-24.txt AC 3 ms 1024 KB
01-25.txt AC 3 ms 1024 KB
01-26.txt AC 1 ms 128 KB
01-27.txt AC 1 ms 512 KB
01-28.txt AC 3 ms 1024 KB
01-29.txt AC 3 ms 1024 KB
01-30.txt AC 3 ms 1024 KB
01-31.txt AC 1 ms 128 KB
01-32.txt AC 3 ms 1024 KB
01-33.txt AC 1 ms 128 KB
01-34.txt AC 3 ms 1024 KB
01-35.txt AC 2 ms 1024 KB
01-36.txt AC 2 ms 1024 KB
01-37.txt AC 1 ms 128 KB
01-38.txt AC 2 ms 1024 KB
01-39.txt AC 2 ms 1024 KB
01-40.txt AC 4 ms 1024 KB
01-41.txt AC 2 ms 1024 KB
01-42.txt AC 2 ms 1024 KB
01-43.txt AC 2 ms 1024 KB
01-44.txt AC 2 ms 1024 KB
01-45.txt AC 2 ms 1024 KB
01-46.txt AC 2 ms 1024 KB
02-01.txt AC 676 ms 140924 KB
02-02.txt AC 597 ms 141948 KB
02-03.txt AC 461 ms 141948 KB
02-04.txt AC 715 ms 140924 KB
02-05.txt AC 1 ms 508 KB
02-06.txt AC 1 ms 508 KB
02-07.txt AC 213 ms 141948 KB
02-08.txt AC 868 ms 140540 KB
02-09.txt AC 243 ms 141052 KB
02-10.txt AC 236 ms 138748 KB
02-11.txt AC 247 ms 141052 KB
02-12.txt AC 236 ms 138748 KB
sample-01.txt AC 1 ms 128 KB
sample-02.txt AC 1 ms 128 KB