RCO presents 日本橋ハーフマラソン 予選

Submission #1510853

Source codeソースコード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<math.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define FOR(i,a,n) for(i=a;i<n;i++)
void fill(int a[],int b,int c){
	int i;
	FOR(i,0,b)a[i]=c;
	return;
}
typedef struct{
	int x,y,data;
}Pos;
void push(Pos *heap,int *heap_size,int x,int y,int a){
	int i=(*heap_size)++;
	while(i>0){
		int p=(i-1)/2;
		if(heap[p].data>=a) break;
		heap[i]=heap[p];
		i=p;
	}
	heap[i].x=x,heap[i].y=y,heap[i].data=a;
	return;
}
Pos pop(Pos *heap,int *heap_size){
	Pos data=heap[0];
	Pos n=heap[--(*heap_size)];
	int pos=0;
	while(pos*2+1<(*heap_size)){
		int a=pos*2+1;
		int b=pos*2+2;
		if(b<(*heap_size)&&heap[a].data<heap[b].data) a=b;
		if(n.data>=heap[a].data) break;
		heap[pos]=heap[a];
		pos=a;
	}
	heap[pos]=n;
	return data;
}
Pos heap[5000];
int heap_size=0;
char map[50][51];
int used[50][50];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int rx[400][8],ry[400][8];
int size=0;
int dfs(int x,int y,int n){
	int i,nx,ny;
	Pos p;
	rx[size][n]=x+1,ry[size][n]=y+1;
	if(n==7) return 1;
	FOR(i,0,4){
		nx=x+dx[i],ny=y+dy[i];
		if(nx<0||ny<0||nx>=50||ny>=50||used[nx][ny]||map[nx][ny]=='0') continue;
		used[nx][ny]=1;
		push(heap,&heap_size,nx,ny,map[nx][ny]-'0');
	}
	if(heap_size==0) return 0;
	p=pop(heap,&heap_size);
	return dfs(p.x,p.y,n+1);
}
int main(void){
	int h,w,n,i,j,k;
	Pos p;
	scanf("%d%d%d",&h,&w,&n);
	FOR(i,0,50) scanf("%s",map[i]);
	for(i==9;i>=1;i--){
		FOR(j,0,50){
			FOR(k,0,50){
				if(map[j][k]-'0'==i&&!used[j][k]){
					heap_size=0; used[j][k]=1;
					if(dfs(j,k,0)) size++;
					while(heap_size){
						p=pop(heap,&heap_size);
						used[p.x][p.y]=0;
					}
				}
			}
		}
	}
	printf("%d\n",size);
	FOR(i,0,size){
		FOR(j,0,8){
			printf("%d %d\n",rx[i][j],ry[i][j]);
		}
	}
}
    

Submission

Task問題 A - Multiple Pieces
User nameユーザ名 stranger
Created time投稿日時
Language言語 C (GCC 5.4.1)
Status状態 AC
Score得点 782986
Source lengthソースコード長 1990 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 256 KB

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

./Main.c: In function ‘main’:
./Main.c:71:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&h,&w,&n);
^
./Main.c:72:14: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
FOR(i,0,50) scanf("%s",map[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
test_01 78452 / 1343058 subtask_01_01.txt
test_02 71559 / 1343058 subtask_01_02.txt
test_03 79806 / 1343058 subtask_01_03.txt
test_04 75521 / 1343058 subtask_01_04.txt
test_05 88325 / 1343058 subtask_01_05.txt
test_06 75772 / 1343058 subtask_01_06.txt
test_07 83886 / 1343058 subtask_01_07.txt
test_08 71830 / 1343058 subtask_01_08.txt
test_09 78508 / 1343058 subtask_01_09.txt
test_10 79327 / 1343058 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 1 ms 256 KB
subtask_01_02.txt AC 1 ms 256 KB
subtask_01_03.txt AC 1 ms 256 KB
subtask_01_04.txt AC 1 ms 256 KB
subtask_01_05.txt AC 1 ms 256 KB
subtask_01_06.txt AC 1 ms 256 KB
subtask_01_07.txt AC 1 ms 256 KB
subtask_01_08.txt AC 1 ms 256 KB
subtask_01_09.txt AC 1 ms 256 KB
subtask_01_10.txt AC 1 ms 256 KB