Submission #2506251

---

Source Code Expand

//HeavyTrafficJamOnNihonbashi
//
//Constraints:
//H = 30
//W = 30
//K = 450
//T = 10000
//
//Scoring Method:
//P_D = 20.0 + (sum of (Manhattan distance between every car's destination and actual position after movement))
//P_T = 10.0 + L * 0.01 (L is the number of movement)
//total score = 10.0 ^ 7 / (P_D + P_T)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
static const int MAX_K = 450;
struct Car{int a, b, c, d, num;};

int H, W, K, T;
Car car[MAX_K];

bool comp(const Car &c1, const Car &c2){
	return (abs(c1.a - c1.c) + abs(c1.b - c1.d)) > (abs(c2.a - c2.c) + abs(c2.b - c2.d));
}

int main(){
	//int total_manhattan_distance = 0;
	int decrease_manhattan_distance = 0;
	cin >> H >> W >> K >> T;
	for(int i = 0; i < K; i++){
		cin >> car[i].a >> car[i].b >> car[i].c >> car[i].d;
		car[i].a--; car[i].b--; car[i].c--; car[i].d--;
		//total_manhattan_distance += abs(car[i].a - car[i].c) + abs(car[i].b - car[i].d);
		car[i].num = i;
	}

	int L = 0;
	vector<string> ans;
	for(int i = 0; i < T; i++){
		string s;
		map<P, int> mp;

		s.resize(K);
		sort(car, car + K, comp);

		int num_movement = 0;
		for(int j = 0; j < K; j++){
			mp[P(car[j].a, car[j].b)]++;
		}
		for(int j = 0; j < K; j++){
			if(abs(car[j].a - car[j].c) > abs(car[j].b - car[j].d)){
				if(car[j].a > car[j].c && mp[P(car[j].a - 1, car[j].b)] == 0){
					s[car[j].num] = 'U';
					mp[P(car[j].a - 1, car[j].b)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].a--;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].a < car[j].c && mp[P(car[j].a + 1, car[j].b)] == 0){
					s[car[j].num] = 'D';
					mp[P(car[j].a + 1, car[j].b)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].a++;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].b > car[j].d && mp[P(car[j].a, car[j].b - 1)] == 0){
					s[car[j].num] = 'L';
					mp[P(car[j].a, car[j].b - 1)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].b--;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].b < car[j].d && mp[P(car[j].a, car[j].b + 1)] == 0){
					s[car[j].num] = 'R';
					mp[P(car[j].a, car[j].b + 1)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].b++;
					num_movement++;
					decrease_manhattan_distance++;
				}else{
					s[car[j].num] = '-';
				}
			}else{
				if(car[j].b > car[j].d && mp[P(car[j].a, car[j].b - 1)] == 0){
					s[car[j].num] = 'L';
					mp[P(car[j].a, car[j].b - 1)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].b--;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].b < car[j].d && mp[P(car[j].a, car[j].b + 1)] == 0){
					s[car[j].num] = 'R';
					mp[P(car[j].a, car[j].b + 1)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].b++;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].a > car[j].c && mp[P(car[j].a - 1, car[j].b)] == 0){
					s[car[j].num] = 'U';
					mp[P(car[j].a - 1, car[j].b)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].a--;
					num_movement++;
					decrease_manhattan_distance++;
				}else if(car[j].a < car[j].c && mp[P(car[j].a + 1, car[j].b)] == 0){
					s[car[j].num] = 'D';
					mp[P(car[j].a + 1, car[j].b)]++;
					mp[P(car[j].a, car[j].b)]--;
					car[j].a++;
					num_movement++;
					decrease_manhattan_distance++;
				}else{
					s[car[j].num] = '-';
				}
			}
		}
		if(num_movement == 0) break;
		L++;
		ans.push_back(s);
	}
	cout << L << endl;
	for(int i = 0; i < L; i++) cout << ans[i] << endl;
	return 0;
}

Submission Info

Judge Result