Submission #1173709
Source Code Expand
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int dx[] = {0, +1, 0, -1, 0};
const int dy[] = {-1, 0, +1, 0, 0};
const string DIRS = "URDL-";
const int MAX_HW = 30;
class XorShift {
static const int MAX = numeric_limits<int>::max();
int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
public:
XorShift() {}
XorShift(int seed) {
x ^= seed;
y ^= x << 10 & seed;
w ^= y >> 20 | seed;
z ^= w & x;
}
int next() {
int t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int next(int min_value, int max_value) {
int range = max_value - min_value;
return (sample() * range) + min_value;
}
double sample() { return next() * 1.0 / MAX; }
} rnd;
//get millsec
#include <sys/time.h>
class Timer {
public:
Timer() {}
void start() { start_time = get_mill_sec(); }
//millsec
double get_duration() { return get_mill_sec() - start_time; }
void set_time_limit(double limit){time_limit = limit;}
bool is_time_limit_exceeded(){return get_duration() > time_limit;}
private:
double start_time;
double time_limit;
double get_mill_sec() {
struct timeval res;
gettimeofday(&res, NULL);
return res.tv_sec * 1000 + res.tv_usec / 1000;
}
} timer;
struct Car{
int idx;
pii src;
pii goal;
Car(){}
Car(int idx, pii src, pii goal):idx(idx),src(src),goal(goal){}
bool operator < (const Car &right) const {
int cost1 = abs(src.first - goal.first) + (src.second - goal.second);
int cost2 = abs(right.src.first - right.goal.first) + (right.src.second - right.goal.second);
if (cost1 != cost2){
return cost1 < cost2;
}
return idx < right.idx;
}
};
bool is_out(int y, int x){
if (y < 0 or y >= MAX_HW or x < 0 or x >= MAX_HW){
return true;
}
return false;
}
vector<Car> input(){
vector<Car> cars;
int H,W,K,T;
cin >> H >> W >> K >> T;
for (int i = 0; i < K; i++){
int A,B,C,D;
cin >> A >> B >> C >> D;
A--,B--,C--,D--;
cars.emplace_back(Car(i, mp(A,B), mp(C, D)));
}
return cars;
}
struct State{
vector<Car> cars;
double score;
shared_ptr<State> parent;
bitset<900> visited;//30 x 30
State(){
}
// State(const State& state):cars(state.cars),score(state.score),visited(state.visited){
// this->parent = NULL;
// }
bool operator < (const State &right) const {
return score < right.score;
}
};
double calc_score(const vector<Car> &cars, int L){
double score = 1e7;
int PD = 20;
int PL = 10 + 0.01 * L;
for (const Car &car : cars){
int diff_y = abs(car.src.first - car.goal.first);
int diff_x = abs(car.src.second - car.goal.second);
PD += diff_x + diff_y;
}
return score / (PD * PL);
}
void simulate_next_state(const State &state, priority_queue<State> &beams, int L){
State next_state(state);
next_state.parent = make_shared<State>(state);
vector<Car>& cars = next_state.cars;
for (Car &car : cars){
int next_dir = rnd.next() % 5;
int y = car.src.first;
int x = car.src.second;
int ny = y + dy[next_dir];
int nx = x + dx[next_dir];
if (is_out(ny, nx))continue;
if (next_state.visited[ny * MAX_HW + nx]){
continue;
}
next_state.visited[ny * MAX_HW + nx] = true;
car.src = mp(ny, nx);
// car.src.first = ny;
// car.src.second = nx;
}
next_state.visited.reset();
for (const Car &car : cars){
int y,x;
y = car.src.first;
x = car.src.second;
next_state.visited[y * MAX_HW + x] = true;
}
next_state.score = calc_score(next_state.cars, L);
beams.emplace(next_state);
}
vector<string> restore_path(const State &state){
vector<string> results;
vector<vector<pii>> paths;
/////////////////////////////////
vector<pii> p;
for (int i = 0; i < state.cars.size(); i++){
p.emplace_back(state.cars[i].src);
}
paths.emplace_back(p);
//////////////////////////////////
for (const State *pos = &state;; pos = pos->parent.get()){
if (pos == NULL){
break;
}
const vector<Car>& cars = pos->cars;
vector<pii> path;
for (const Car &car : cars){
path.emplace_back(car.src);
}
paths.push_back(move(path));
}
reverse(paths.begin(), paths.end());
// cout << paths.size() << endl;
for (int i = 0; i < paths.size() - 1; i++){
string command = "";
for (int j = 0; j < paths[i].size(); j++){
pii pos = paths[i][j];
pii goal = paths[i + 1][j];
// cout << pos.first << " " << pos.second << endl;
// cout << goal.first << " " << goal.second << endl;
// // cout << endl;
// assert(pos == goal);
for (int k = 0; k < 5; k++){
int y = pos.first + dy[k];
int x = pos.second + dx[k];
if (y == goal.first and x == goal.second){
command += DIRS[k];
break;
}
}
}
results.emplace_back(command);
}
return results;
}
void output_command(const vector<string> &commands){
cout << commands.size() << endl;
for (const string &command : commands){
cout << command << endl;
}
}
void solve(vector<Car> cars, int limit){
State root;
root.cars = cars;
for (Car &car : cars){
int y,x;
y = car.src.first;
x = car.src.second;
root.visited[y * MAX_HW + x] = true;
}
State best_state = root;
double best_score = calc_score(root.cars, 0);
root.score = best_score;
priority_queue<State> beams[2];
beams[0].emplace(root);
timer.start();
int cho_iter = 0;
while (timer.get_duration() < 2000){
for (int depth = 0; depth < 1500; depth++){
int cur_depth = depth % 2;
int next_depth = (depth + 1) % 2;
for (int iter = 0; iter < 5 and (not beams[cur_depth].empty()); iter++){
State state = beams[cur_depth].top();
if (best_score < state.score){
best_score = state.score;
best_state = state;
// cout << calc_score(best_state.cars, depth) << " " << best_score << " " << depth << endl;
// output_command(restore_path(best_state));
}
beams[cur_depth].pop();
for (int j = 0; j < 20; j++){
simulate_next_state(state, beams[next_depth], depth + 1);
}
}
while (not beams[cur_depth].empty())beams[cur_depth].pop();
}
cho_iter++;
break;
}
vector<string> commands = restore_path(best_state);
output_command(commands);
cerr << best_score << endl;
}
int main() {
vector<Car> cars = input();
solve(cars, 114514);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
togatoga |
Language |
C++14 (GCC 5.4.1) |
Score |
5518 |
Code Size |
7480 Byte |
Status |
AC |
Exec Time |
1287 ms |
Memory |
24288 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 |
186 / 50000 |
199 / 50000 |
196 / 50000 |
206 / 50000 |
193 / 50000 |
194 / 50000 |
157 / 50000 |
183 / 50000 |
182 / 50000 |
178 / 50000 |
185 / 50000 |
189 / 50000 |
177 / 50000 |
195 / 50000 |
195 / 50000 |
190 / 50000 |
187 / 50000 |
176 / 50000 |
171 / 50000 |
180 / 50000 |
175 / 50000 |
181 / 50000 |
180 / 50000 |
174 / 50000 |
180 / 50000 |
175 / 50000 |
200 / 50000 |
166 / 50000 |
179 / 50000 |
189 / 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 |
1274 ms |
22224 KB |
subtask_01_02.txt |
AC |
1283 ms |
22144 KB |
subtask_01_03.txt |
AC |
1280 ms |
21768 KB |
subtask_01_04.txt |
AC |
1280 ms |
22772 KB |
subtask_01_05.txt |
AC |
1276 ms |
22224 KB |
subtask_01_06.txt |
AC |
1276 ms |
22624 KB |
subtask_01_07.txt |
AC |
1265 ms |
23284 KB |
subtask_01_08.txt |
AC |
1276 ms |
23132 KB |
subtask_01_09.txt |
AC |
1277 ms |
23284 KB |
subtask_01_10.txt |
AC |
1271 ms |
23220 KB |
subtask_01_11.txt |
AC |
1278 ms |
23124 KB |
subtask_01_12.txt |
AC |
1278 ms |
23136 KB |
subtask_01_13.txt |
AC |
1273 ms |
22272 KB |
subtask_01_14.txt |
AC |
1280 ms |
22108 KB |
subtask_01_15.txt |
AC |
1277 ms |
23188 KB |
subtask_01_16.txt |
AC |
1275 ms |
22752 KB |
subtask_01_17.txt |
AC |
1274 ms |
22744 KB |
subtask_01_18.txt |
AC |
1268 ms |
22160 KB |
subtask_01_19.txt |
AC |
1269 ms |
23212 KB |
subtask_01_20.txt |
AC |
1275 ms |
23188 KB |
subtask_01_21.txt |
AC |
1271 ms |
23152 KB |
subtask_01_22.txt |
AC |
1272 ms |
22784 KB |
subtask_01_23.txt |
AC |
1272 ms |
22168 KB |
subtask_01_24.txt |
AC |
1269 ms |
22724 KB |
subtask_01_25.txt |
AC |
1276 ms |
23284 KB |
subtask_01_26.txt |
AC |
1275 ms |
23032 KB |
subtask_01_27.txt |
AC |
1287 ms |
24288 KB |
subtask_01_28.txt |
AC |
1266 ms |
23228 KB |
subtask_01_29.txt |
AC |
1270 ms |
23272 KB |
subtask_01_30.txt |
AC |
1282 ms |
23276 KB |