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

Submission #2503934

Source codeソースコード

//HeavyTrafficJamOnNihonbashi
//
//Constraints:
//H = 30
//W = 30
//K = 450
//T = 10000
//
//Scoring Method:
//P_D = 20.0 + (sum of (Manhatthan 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_manhatthan_distance = 0;
	int decrease_manhatthan_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_manhatthan_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_manhatthan_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_manhatthan_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_manhatthan_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_manhatthan_distance++;
				}else{
					s[car[j].num] = '-';
				}
			}
		}
		if(num_movement < (double)decrease_manhatthan_distance * 0.01) break;
		L++;
		ans.push_back(s);
	}
	cout << L << endl;
	for(int i = 0; i < L; i++) cout << ans[i] << endl;
	return 0;
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
test_01 0 / 50000 subtask_01_01.txt
test_02 0 / 50000 subtask_01_02.txt
test_03 0 / 50000 subtask_01_03.txt
test_04 0 / 50000 subtask_01_04.txt
test_05 0 / 50000 subtask_01_05.txt
test_06 0 / 50000 subtask_01_06.txt
test_07 0 / 50000 subtask_01_07.txt
test_08 0 / 50000 subtask_01_08.txt
test_09 0 / 50000 subtask_01_09.txt
test_10 0 / 50000 subtask_01_10.txt
test_11 0 / 50000 subtask_01_11.txt
test_12 0 / 50000 subtask_01_12.txt
test_13 0 / 50000 subtask_01_13.txt
test_14 0 / 50000 subtask_01_14.txt
test_15 0 / 50000 subtask_01_15.txt
test_16 0 / 50000 subtask_01_16.txt
test_17 0 / 50000 subtask_01_17.txt
test_18 0 / 50000 subtask_01_18.txt
test_19 0 / 50000 subtask_01_19.txt
test_20 0 / 50000 subtask_01_20.txt
test_21 0 / 50000 subtask_01_21.txt
test_22 0 / 50000 subtask_01_22.txt
test_23 0 / 50000 subtask_01_23.txt
test_24 0 / 50000 subtask_01_24.txt
test_25 0 / 50000 subtask_01_25.txt
test_26 0 / 50000 subtask_01_26.txt
test_27 0 / 50000 subtask_01_27.txt
test_28 0 / 50000 subtask_01_28.txt
test_29 0 / 50000 subtask_01_29.txt
test_30 0 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt WA
subtask_01_02.txt WA
subtask_01_03.txt WA
subtask_01_04.txt WA
subtask_01_05.txt WA
subtask_01_06.txt WA
subtask_01_07.txt WA
subtask_01_08.txt WA
subtask_01_09.txt WA
subtask_01_10.txt WA
subtask_01_11.txt WA
subtask_01_12.txt WA
subtask_01_13.txt WA
subtask_01_14.txt WA
subtask_01_15.txt WA
subtask_01_16.txt WA
subtask_01_17.txt WA
subtask_01_18.txt WA
subtask_01_19.txt WA
subtask_01_20.txt WA
subtask_01_21.txt WA
subtask_01_22.txt WA
subtask_01_23.txt WA
subtask_01_24.txt WA
subtask_01_25.txt WA
subtask_01_26.txt WA
subtask_01_27.txt WA
subtask_01_28.txt WA
subtask_01_29.txt WA
subtask_01_30.txt WA