Submission #1174244
Source Code Expand
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct State {
int turn;
int dist;
int x[450];
int y[450];
double get_score() {
return 1e7 / (dist * (10 + turn * 0.01));
}
};
int H, W, K, T;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char direction[5] = "RDLU";
int dest_x[450];
int dest_y[450];
bool used[30][30];
void solve(State &state) {
int i, j, k, l;
double best_score = state.get_score();
vector <string> ans;
vector <int> order;
for (i = 0; i < K; i++) order.push_back(i);
for (i = 0; i < T; i++) {
double next_score = best_score;
State next_state;
string next_movement;
int loop;
if (i < 20) {
loop = 500;
} else {
loop = 10;
}
for (j = 0; j < loop; j++) {
random_shuffle(order.begin(), order.end());
for (k = 0; k < H; k++) {
for (l = 0; l < W; l++) {
used[k][l] = false;
}
}
for (k = 0; k < K; k++) used[state.x[k]][state.y[k]] = true;
int move_dist = 0;
string movement = string(K, '-');
for (k = 0; k < K; k++) {
int pos = order[k];
for (l = 0; l < 4; l++) {
int x = state.x[pos];
int y = state.y[pos];
int nx = x + dx[l];
int ny = y + dy[l];
if (nx < 0 || nx >= H || ny < 0 || ny >= W || used[nx][ny] == true) continue;
if (abs(x - dest_x[pos]) + abs(y - dest_y[pos]) > abs(nx - dest_x[pos]) + abs(ny - dest_y[pos])) {
used[nx][ny] = true;
state.x[pos] = nx;
state.y[pos] = ny;
move_dist++;
movement[pos] = direction[l];
break;
}
}
}
state.turn++;
state.dist -= move_dist;
double score = state.get_score();
if (score > next_score) {
next_score = score;
next_state = state;
next_movement = movement;
}
state.turn--;
state.dist += move_dist;
for (k = 0; k < K; k++) {
if (movement[k] == '-') continue;
if (movement[k] == 'R') {
state.y[k]--;
} else if (movement[k] == 'D') {
state.x[k]--;
} else if (movement[k] == 'L') {
state.y[k]++;
} else {
state.x[k]++;
}
}
}
if (next_score > best_score) {
best_score = next_score;
state = next_state;
ans.push_back(next_movement);
}
}
printf("%d\n", ans.size());
for (i = 0; i < ans.size(); i++) printf("%s\n", ans[i].c_str());
}
int main() {
int i;
scanf("%d %d %d %d", &H, &W, &K, &T);
State state;
state.turn = 0;
state.dist = 20;
for (i = 0; i < K; i++) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
a--;
b--;
c--;
d--;
state.x[i] = a;
state.y[i] = b;
dest_x[i] = c;
dest_y[i] = d;
state.dist += abs(a - c) + abs(b - d);
}
solve(state);
return 0;
}
Submission Info
Submission Time
2017-03-20 17:51:23+0900
Task
B - 日本橋大渋滞
User
kawatea
Language
C++14 (GCC 5.4.1)
Score
4711
Code Size
3990 Byte
Status
AC
Exec Time
2455 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘void solve(State&)’:
./Main.cpp:118:30: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
printf("%d\n", ans.size());
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:125:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &H, &W, &K, &T);
^
./Main.cpp:134:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &a, &b, &c, &d);
^
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
160 / 50000
163 / 50000
163 / 50000
178 / 50000
154 / 50000
157 / 50000
169 / 50000
151 / 50000
156 / 50000
162 / 50000
156 / 50000
154 / 50000
167 / 50000
149 / 50000
167 / 50000
154 / 50000
149 / 50000
154 / 50000
150 / 50000
164 / 50000
152 / 50000
153 / 50000
149 / 50000
148 / 50000
161 / 50000
156 / 50000
144 / 50000
156 / 50000
151 / 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
AC
2367 ms
256 KB
subtask_01_02.txt
AC
2349 ms
256 KB
subtask_01_03.txt
AC
2336 ms
256 KB
subtask_01_04.txt
AC
2347 ms
256 KB
subtask_01_05.txt
AC
2423 ms
256 KB
subtask_01_06.txt
AC
2355 ms
256 KB
subtask_01_07.txt
AC
2328 ms
256 KB
subtask_01_08.txt
AC
2344 ms
256 KB
subtask_01_09.txt
AC
2339 ms
256 KB
subtask_01_10.txt
AC
2391 ms
256 KB
subtask_01_11.txt
AC
2348 ms
256 KB
subtask_01_12.txt
AC
2324 ms
256 KB
subtask_01_13.txt
AC
2316 ms
256 KB
subtask_01_14.txt
AC
2419 ms
256 KB
subtask_01_15.txt
AC
2313 ms
256 KB
subtask_01_16.txt
AC
2455 ms
256 KB
subtask_01_17.txt
AC
2293 ms
256 KB
subtask_01_18.txt
AC
2337 ms
256 KB
subtask_01_19.txt
AC
2278 ms
256 KB
subtask_01_20.txt
AC
2320 ms
256 KB
subtask_01_21.txt
AC
2358 ms
256 KB
subtask_01_22.txt
AC
2314 ms
256 KB
subtask_01_23.txt
AC
2237 ms
256 KB
subtask_01_24.txt
AC
2275 ms
256 KB
subtask_01_25.txt
AC
2375 ms
256 KB
subtask_01_26.txt
AC
2357 ms
256 KB
subtask_01_27.txt
AC
2340 ms
256 KB
subtask_01_28.txt
AC
2294 ms
256 KB
subtask_01_29.txt
AC
2380 ms
256 KB
subtask_01_30.txt
AC
2295 ms
256 KB