Submission #1173448


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)
const int DX[4] = {0,1,0,-1}, DY[4] = {-1,0,1,0};
template< typename T >
inline bool in_range(T v, T mi, T mx) { return mi <= v && v < mx; }
template< typename T >
inline bool in_range(T x, T y, T W, T H) { return in_range(x,0,W) && in_range(y,0,H); }



//
string movestr = "URDL-";
int H, W, K, T, A[450], B[450], C[450], D[450];
bool board[33][33];

void construct() {
	memset(board, 0, sizeof(board));
	for_(i,0,K) board[A[i]][B[i]] = true;
}

void greedyMovement() {
	vector< string > ans;
	
	for_(rep,0,T) {
		string movement;
		
		construct();
		
		for_(i,0,K) {
			int cur_dst = abs(C[i] - A[i]) + abs(D[i] - B[i]);
			
			bool move_flag = false;
			for_(d,0,4) {
				int nx = B[i] + DX[d], ny = A[i] + DY[d];
				if (!in_range(nx, ny, W, H)) continue;
				if (board[ny][nx]) continue;
				int nxt_dst = abs(C[i] - ny) + abs(D[i] - nx);
				
				if (nxt_dst < cur_dst) {
					// move
					movement += movestr[d];
					A[i] = ny;
					B[i] = nx;
					move_flag = true;
					board[ny][nx] = true;
					break;
				}
			}
			
			if (!move_flag) movement += "-";
		}
		
		bool end = true;
		for_(i,0,K) end &= (movement[i] == '-');
		if (end) break;
		
		ans.push_back(movement);
	}
	
	int m = ans.size();
	cout << m << endl;
	for_(i,0,m) cout << ans[i] << endl;
}

int main() {
	cin >> H >> W >> K >> T;
	for_(i,0,K) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		--A[i]; --B[i]; --C[i]; --D[i];
	}
	greedyMovement();
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User tsukasa_diary
Language C++14 (GCC 5.4.1)
Score 4655
Code Size 1584 Byte
Status AC
Exec Time 2 ms
Memory 256 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 164 / 50000 159 / 50000 156 / 50000 162 / 50000 172 / 50000 156 / 50000 156 / 50000 165 / 50000 148 / 50000 148 / 50000 164 / 50000 160 / 50000 149 / 50000 165 / 50000 147 / 50000 166 / 50000 150 / 50000 148 / 50000 154 / 50000 151 / 50000 159 / 50000 152 / 50000 150 / 50000 143 / 50000 151 / 50000 156 / 50000 154 / 50000 142 / 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 2 ms 256 KB
subtask_01_02.txt AC 2 ms 256 KB
subtask_01_03.txt AC 2 ms 256 KB
subtask_01_04.txt AC 2 ms 256 KB
subtask_01_05.txt AC 2 ms 256 KB
subtask_01_06.txt AC 2 ms 256 KB
subtask_01_07.txt AC 2 ms 256 KB
subtask_01_08.txt AC 2 ms 256 KB
subtask_01_09.txt AC 2 ms 256 KB
subtask_01_10.txt AC 2 ms 256 KB
subtask_01_11.txt AC 2 ms 256 KB
subtask_01_12.txt AC 2 ms 256 KB
subtask_01_13.txt AC 2 ms 256 KB
subtask_01_14.txt AC 2 ms 256 KB
subtask_01_15.txt AC 2 ms 256 KB
subtask_01_16.txt AC 2 ms 256 KB
subtask_01_17.txt AC 2 ms 256 KB
subtask_01_18.txt AC 2 ms 256 KB
subtask_01_19.txt AC 2 ms 256 KB
subtask_01_20.txt AC 2 ms 256 KB
subtask_01_21.txt AC 2 ms 256 KB
subtask_01_22.txt AC 2 ms 256 KB
subtask_01_23.txt AC 2 ms 256 KB
subtask_01_24.txt AC 2 ms 256 KB
subtask_01_25.txt AC 2 ms 256 KB
subtask_01_26.txt AC 2 ms 256 KB
subtask_01_27.txt AC 2 ms 256 KB
subtask_01_28.txt AC 2 ms 256 KB
subtask_01_29.txt AC 2 ms 256 KB
subtask_01_30.txt AC 2 ms 256 KB