Submission #1186401


Source Code Expand

#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 Info

Submission Time
Task B - 日本橋大渋滞
User E869120
Language C++14 (GCC 5.4.1)
Score 27302
Code Size 1902 Byte
Status AC
Exec Time 347 ms
Memory 9600 KB

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 1696 / 50000 989 / 50000 1352 / 50000 1204 / 50000 1181 / 50000 244 / 50000 183 / 50000 866 / 50000 208 / 50000 908 / 50000 1511 / 50000 1352 / 50000 1172 / 50000 910 / 50000 188 / 50000 1093 / 50000 174 / 50000 945 / 50000 1262 / 50000 188 / 50000 1230 / 50000 1179 / 50000 195 / 50000 1331 / 50000 1153 / 50000 1291 / 50000 813 / 50000 1064 / 50000 552 / 50000 868 / 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 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