Submission #1186390


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 (dist(j, k, c[num], d[num]) >= H)YY = 4;
					else if (i <= 3000)YY = 7;
					else YY = 60;*/

					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 17250
Code Size 1980 Byte
Status AC
Exec Time 315 ms
Memory 9472 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 1116 / 50000 648 / 50000 1253 / 50000 874 / 50000 833 / 50000 224 / 50000 384 / 50000 776 / 50000 449 / 50000 413 / 50000 450 / 50000 681 / 50000 537 / 50000 463 / 50000 180 / 50000 379 / 50000 267 / 50000 524 / 50000 637 / 50000 348 / 50000 916 / 50000 427 / 50000 554 / 50000 723 / 50000 523 / 50000 1245 / 50000 567 / 50000 186 / 50000 186 / 50000 487 / 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 312 ms 6272 KB
subtask_01_02.txt AC 306 ms 6784 KB
subtask_01_03.txt AC 314 ms 5888 KB
subtask_01_04.txt AC 309 ms 6016 KB
subtask_01_05.txt AC 309 ms 6272 KB
subtask_01_06.txt AC 282 ms 5760 KB
subtask_01_07.txt AC 291 ms 8576 KB
subtask_01_08.txt AC 307 ms 6400 KB
subtask_01_09.txt AC 303 ms 8448 KB
subtask_01_10.txt AC 299 ms 8576 KB
subtask_01_11.txt AC 311 ms 8320 KB
subtask_01_12.txt AC 311 ms 7296 KB
subtask_01_13.txt AC 311 ms 7936 KB
subtask_01_14.txt AC 308 ms 8064 KB
subtask_01_15.txt AC 267 ms 5248 KB
subtask_01_16.txt AC 315 ms 9472 KB
subtask_01_17.txt AC 293 ms 7424 KB
subtask_01_18.txt AC 306 ms 7424 KB
subtask_01_19.txt AC 306 ms 6528 KB
subtask_01_20.txt AC 301 ms 8832 KB
subtask_01_21.txt AC 312 ms 6400 KB
subtask_01_22.txt AC 305 ms 8448 KB
subtask_01_23.txt AC 299 ms 7552 KB
subtask_01_24.txt AC 305 ms 6912 KB
subtask_01_25.txt AC 308 ms 7680 KB
subtask_01_26.txt AC 313 ms 6016 KB
subtask_01_27.txt AC 313 ms 7168 KB
subtask_01_28.txt AC 279 ms 5248 KB
subtask_01_29.txt AC 282 ms 5248 KB
subtask_01_30.txt AC 296 ms 7680 KB