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

Submission #1186401

Source codeソースコード

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<ctime>
using namespace std;
#pragma warning(disable:4996)
/*FILE *in = freopen("in1.txt", "r", stdin);
FILE *out = freopen("out1.txt", "w", stdout);*/

int H, W, K, T, a[453], b[453], c[453], d[453], I[33][33], dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
char Y[5] = "URDL"; bool used[33][33];
int score() {
	int ret = 0;
	for (int i = 1; i <= K; i++)ret += abs(a[i] - c[i]) + abs(b[i] - d[i]);
	return ret + 20;
}
int dist(int a1, int a2, int a3, int a4) { return abs(a1 - a3) + abs(a2 - a4); }
int main() {
	srand((unsigned)time(NULL));
	cin >> H >> W >> K >> T;
	for (int i = 1; i <= K; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; I[a[i]][b[i]] = i; }
	int maxn = 0, maxid = score(); vector<string>V;
	for (int i = 1; i <= T; i++) {
		string O = ""; for (int j = 0; j < K; j++)O += " ";
		for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++)used[j][k] = false; }
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				if (I[j][k] == 0 || O[I[j][k] - 1] != ' ')continue;
				bool OK = true;
				for (int l = 0; l < 4; l++) {
					int cx = j + dx[l], cy = k + dy[l], num = I[j][k];
					if (cx <= 0 || cy <= 0 || cx > H || cy > W || I[cx][cy] >= 1 || used[cx][cy] == true)continue;

					int YY = 5;
					if (i >= 9000)YY = 15;

					if (dist(cx, cy, c[I[j][k]], d[num]) > dist(j, k, c[num], d[num]) && rand()%YY < (YY - 1))continue;
					O[num - 1] = Y[l]; a[num] = cx; b[num] = cy; swap(I[cx][cy], I[j][k]); used[j][k] = true;
					OK = false; break;
				}
				if (OK == true)O[I[j][k] - 1] = '-';
			}
		}
		V.push_back(O);
		int score2 = 1000000000 / ((score())*(1000 + i));
		if (maxn < score2) { maxn = score2; maxid = i; }
	}
	cout << maxid << endl;
	for (int i = 0; i < maxid; i++) { cout << V[i] << endl; }
	return 0;
}

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 E869120
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 27302
Source lengthソースコード長 1902 Byte
File nameファイル名
Exec time実行時間 347 ms
Memory usageメモリ使用量 9600 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 1696 / 50000 subtask_01_01.txt
test_02 989 / 50000 subtask_01_02.txt
test_03 1352 / 50000 subtask_01_03.txt
test_04 1204 / 50000 subtask_01_04.txt
test_05 1181 / 50000 subtask_01_05.txt
test_06 244 / 50000 subtask_01_06.txt
test_07 183 / 50000 subtask_01_07.txt
test_08 866 / 50000 subtask_01_08.txt
test_09 208 / 50000 subtask_01_09.txt
test_10 908 / 50000 subtask_01_10.txt
test_11 1511 / 50000 subtask_01_11.txt
test_12 1352 / 50000 subtask_01_12.txt
test_13 1172 / 50000 subtask_01_13.txt
test_14 910 / 50000 subtask_01_14.txt
test_15 188 / 50000 subtask_01_15.txt
test_16 1093 / 50000 subtask_01_16.txt
test_17 174 / 50000 subtask_01_17.txt
test_18 945 / 50000 subtask_01_18.txt
test_19 1262 / 50000 subtask_01_19.txt
test_20 188 / 50000 subtask_01_20.txt
test_21 1230 / 50000 subtask_01_21.txt
test_22 1179 / 50000 subtask_01_22.txt
test_23 195 / 50000 subtask_01_23.txt
test_24 1331 / 50000 subtask_01_24.txt
test_25 1153 / 50000 subtask_01_25.txt
test_26 1291 / 50000 subtask_01_26.txt
test_27 813 / 50000 subtask_01_27.txt
test_28 1064 / 50000 subtask_01_28.txt
test_29 552 / 50000 subtask_01_29.txt
test_30 868 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 332 ms 5632 KB
subtask_01_02.txt AC 339 ms 9600 KB
subtask_01_03.txt AC 336 ms 9216 KB
subtask_01_04.txt AC 347 ms 9344 KB
subtask_01_05.txt AC 335 ms 9344 KB
subtask_01_06.txt AC 304 ms 5504 KB
subtask_01_07.txt AC 260 ms 5248 KB
subtask_01_08.txt AC 338 ms 9472 KB
subtask_01_09.txt AC 273 ms 5248 KB
subtask_01_10.txt AC 327 ms 9344 KB
subtask_01_11.txt AC 343 ms 9344 KB
subtask_01_12.txt AC 339 ms 9344 KB
subtask_01_13.txt AC 336 ms 9472 KB
subtask_01_14.txt AC 337 ms 9344 KB
subtask_01_15.txt AC 263 ms 5248 KB
subtask_01_16.txt AC 340 ms 9344 KB
subtask_01_17.txt AC 280 ms 5248 KB
subtask_01_18.txt AC 325 ms 9344 KB
subtask_01_19.txt AC 334 ms 9472 KB
subtask_01_20.txt AC 283 ms 5376 KB
subtask_01_21.txt AC 328 ms 6016 KB
subtask_01_22.txt AC 329 ms 9344 KB
subtask_01_23.txt AC 285 ms 5248 KB
subtask_01_24.txt AC 341 ms 9216 KB
subtask_01_25.txt AC 333 ms 9600 KB
subtask_01_26.txt AC 330 ms 5888 KB
subtask_01_27.txt AC 334 ms 9344 KB
subtask_01_28.txt AC 324 ms 9472 KB
subtask_01_29.txt AC 318 ms 9344 KB
subtask_01_30.txt AC 318 ms 9344 KB