Submission #2506109
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{
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{
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
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
utsumi |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2711 Byte |
Status |
WA |
Exec Time |
5 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 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
0 / 50000 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |
WA |
4 ms |
256 KB |
subtask_01_02.txt |
WA |
4 ms |
256 KB |
subtask_01_03.txt |
WA |
5 ms |
256 KB |
subtask_01_04.txt |
WA |
4 ms |
256 KB |
subtask_01_05.txt |
WA |
4 ms |
256 KB |
subtask_01_06.txt |
WA |
4 ms |
256 KB |
subtask_01_07.txt |
WA |
3 ms |
256 KB |
subtask_01_08.txt |
WA |
4 ms |
256 KB |
subtask_01_09.txt |
WA |
5 ms |
256 KB |
subtask_01_10.txt |
WA |
4 ms |
256 KB |
subtask_01_11.txt |
WA |
5 ms |
256 KB |
subtask_01_12.txt |
WA |
4 ms |
256 KB |
subtask_01_13.txt |
WA |
4 ms |
256 KB |
subtask_01_14.txt |
WA |
4 ms |
256 KB |
subtask_01_15.txt |
WA |
3 ms |
256 KB |
subtask_01_16.txt |
WA |
4 ms |
256 KB |
subtask_01_17.txt |
WA |
4 ms |
256 KB |
subtask_01_18.txt |
WA |
4 ms |
256 KB |
subtask_01_19.txt |
WA |
4 ms |
256 KB |
subtask_01_20.txt |
WA |
4 ms |
256 KB |
subtask_01_21.txt |
WA |
4 ms |
256 KB |
subtask_01_22.txt |
WA |
4 ms |
256 KB |
subtask_01_23.txt |
WA |
4 ms |
256 KB |
subtask_01_24.txt |
WA |
4 ms |
256 KB |
subtask_01_25.txt |
WA |
4 ms |
256 KB |
subtask_01_26.txt |
WA |
4 ms |
256 KB |
subtask_01_27.txt |
WA |
3 ms |
256 KB |
subtask_01_28.txt |
WA |
3 ms |
256 KB |
subtask_01_29.txt |
WA |
4 ms |
256 KB |
subtask_01_30.txt |
WA |
4 ms |
256 KB |