Submission #3516307
Source Code Expand
#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 Info
Submission Time
2018-11-01 22:37:36+0900
Task
J - Neue Spiel
User
abc050
Language
C (GCC 5.4.1)
Score
2100
Code Size
12578 Byte
Status
AC
Exec Time
868 ms
Memory
141948 KB
Compile Error
./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]);
^
Judge Result
Set Name
sample
dataset1
dataset2
Score / Max Score
0 / 0
2000 / 2000
100 / 100
Status
Set Name
Test Cases
sample
sample-01.txt, sample-02.txt
dataset1
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
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
Case Name
Status
Exec Time
Memory
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