Submission #1173557


Source Code Expand

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

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};
const char *ch = "URDL";

int field[30][30], field_next[30][30];
int ci[450], cj[450], gi[450], gj[450];
char ans[10000][451];

int main(void) {
	int i, j;
	int h, w, k, t;
	int turn;

	scanf("%d %d %d %d", &h, &w, &k, &t);

	for (i = 0; i < h; i++)
		for (j = 0; j < w; j++)
			field_next[i][j] = -1;

	for (i = 0; i < k; i++) {
		scanf("%d %d %d %d", ci + i, cj + i, gi + i, gj + i);
		ci[i]--; cj[i]--; gi[i]--; gj[i]--;
		field_next[ci[i]][cj[i]] = i + 1;
	}

	for (turn = 0; turn < 10000; turn++) {
		int pd;
		double pt, score, score_next;

		pd = 20;
		for (i = 0; i < k; i++)
			pd += abs(gi[i] - ci[i]) + abs(gj[i] - cj[i]);
		pt = 10 + turn * 0.01;
		score = 1e7 / pd / pt;

		fprintf(stderr, "%d\n", pd);
		fprintf(stderr, "%f\n", pt);
		fprintf(stderr, "%f\n", score);

		memcpy(field, field_next, sizeof field);
		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				field_next[i][j] = -1;

		int ii, jj;
		fprintf(stderr, "turn: %d\n", turn);
		for (ii = 0; ii < h; ii++)
			for (jj = 0; jj < w; jj++)
				fprintf(stderr, "%3d%c", field[ii][jj], " \n"[jj == w - 1]);
		fprintf(stderr, "\n");

		for (i = 0; i < k; i++) {
			int moved;

			moved = 0;
			for (j = 0; j < 4; j++) {
				const int ni = ci[i] + di[j], nj = cj[i] + dj[j];
				if (ni >= 0 && ni < h && nj >= 0 && nj < w && field[ni][nj] == -1 && field_next[ni][nj] == -1)
					if (abs(gi[i] - ni) + abs(gj[i] - nj) < abs(gi[i] - ci[i]) + abs(gj[i] - cj[i])) {
						ans[turn][i] = ch[j];
						field_next[ni][nj] = i + 1;
						ci[i] = ni; cj[i] = nj;
						moved = 1;
						break;
					}
			}

			if (!moved) {
				ans[turn][i] = '-';
				field_next[ci[i]][cj[i]] = i + 1;
			}
		}

		pd = 20;
		for (i = 0; i < k; i++)
			pd += abs(gi[i] - ci[i]) + abs(gj[i] - cj[i]);
		pt = 10 + (turn + 1) * 0.01;
		score_next = 1e7 / pd / pt;

		fprintf(stderr, "%d\n", pd);
		fprintf(stderr, "%f\n", pt);
		fprintf(stderr, "%f\n", score_next);

		if (score_next < score)
			break;
	}

	printf("%d\n", turn);
	for (i = 0; i < turn; i++)
		puts(ans[i]);

	return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User zeosutt
Language C (GCC 5.4.1)
Score 4671
Code Size 2255 Byte
Status AC
Exec Time 18 ms
Memory 256 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:18:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &h, &w, &k, &t);
  ^
./Main.c:25:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", ci + i, cj + i, gi + i, gj + i);
   ^

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 165 / 50000 160 / 50000 157 / 50000 163 / 50000 173 / 50000 158 / 50000 156 / 50000 165 / 50000 149 / 50000 149 / 50000 164 / 50000 160 / 50000 150 / 50000 166 / 50000 147 / 50000 166 / 50000 150 / 50000 148 / 50000 154 / 50000 151 / 50000 159 / 50000 152 / 50000 150 / 50000 144 / 50000 152 / 50000 157 / 50000 155 / 50000 143 / 50000 155 / 50000 153 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 14 ms 256 KB
subtask_01_02.txt AC 15 ms 256 KB
subtask_01_03.txt AC 13 ms 256 KB
subtask_01_04.txt AC 17 ms 256 KB
subtask_01_05.txt AC 13 ms 256 KB
subtask_01_06.txt AC 15 ms 256 KB
subtask_01_07.txt AC 13 ms 256 KB
subtask_01_08.txt AC 14 ms 256 KB
subtask_01_09.txt AC 13 ms 256 KB
subtask_01_10.txt AC 14 ms 256 KB
subtask_01_11.txt AC 12 ms 256 KB
subtask_01_12.txt AC 18 ms 256 KB
subtask_01_13.txt AC 14 ms 256 KB
subtask_01_14.txt AC 16 ms 256 KB
subtask_01_15.txt AC 11 ms 256 KB
subtask_01_16.txt AC 12 ms 256 KB
subtask_01_17.txt AC 12 ms 256 KB
subtask_01_18.txt AC 13 ms 256 KB
subtask_01_19.txt AC 15 ms 256 KB
subtask_01_20.txt AC 13 ms 256 KB
subtask_01_21.txt AC 13 ms 256 KB
subtask_01_22.txt AC 14 ms 256 KB
subtask_01_23.txt AC 13 ms 256 KB
subtask_01_24.txt AC 12 ms 256 KB
subtask_01_25.txt AC 14 ms 256 KB
subtask_01_26.txt AC 18 ms 256 KB
subtask_01_27.txt AC 13 ms 256 KB
subtask_01_28.txt AC 16 ms 256 KB
subtask_01_29.txt AC 15 ms 256 KB
subtask_01_30.txt AC 14 ms 256 KB