結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 highjump
|
| 提出日時 | 2022-07-30 16:15:30 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,306 bytes |
| コンパイル時間 | 2,079 ms |
| スコア | 0 |
| 最終ジャッジ日時 | 2022-07-30 16:16:14 |
| 合計ジャッジ時間 | 42,987 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | TLE | - |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | TLE | - |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | TLE | - |
| testcase_11 | TLE | - |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | TLE | - |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
ソースコード
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>using V = vector<T>;
template <class T>using VV = V<V<T>>;
template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }
template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }
#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)
#define MP make_pair
#define SZ(x) int(x.size())
#define ALL(x) x.begin(),x.end()
#define INF 10001000
#define endl "\n"
chrono::system_clock::time_point t_start;
const double TIME_LIMIT1 = 500, TIME_LIMIT = 900;
double last_update = 0, t_diff;
double start_temp, end_temp;
mt19937 rng;
using uni_int = uniform_int_distribution<>;
using uni_real = uniform_real_distribution<>;
using u64 = uint64_t;
using u32 = uint32_t;
V<int> y_vec = { 0, 1,0, -1 };
V<int> x_vec = { -1, 0,1, 0 };
class XorInt {
public:
uint32_t x = 2463534242;
XorInt() {};
XorInt(uint32_t seed) {
x = 2463534242 + seed;
};
uint32_t next() {
x ^= x << 13; x ^= x >> 17; x ^= x << 5;
return x;
}
uint32_t operator()(uint32_t l, uint32_t r) {
return (this->next() % (r - l)) + l;
}
uint32_t operator()(uint32_t d) {
return this->next() % d;
}
};
XorInt xs;
class Xor64 {
public:
uint64_t x = 88172645463325252ULL;
Xor64() {};
Xor64(uint64_t seed) {
x = 88172645463325252ULL + seed;
}
uint64_t next() {
x ^= x << 13; x ^= x >> 7; x ^= x << 17;
return x;
}
uint64_t operator()(uint64_t l, uint64_t r) {
return (this->next() % (r - l)) + l;
}
uint64_t operator()(uint64_t d) {
return this->next() % d;
}
};
Xor64 xx;
void get_time() {
auto t_now = chrono::system_clock::now();
t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}
int N, M;
const int A = 5;
int score = 0;
int bestScore = 0;
int cnt = 0;
class Pos {
public:
int x=0;
int y=0;
int kind = 0;
int order = 0;
Pos() {};
Pos(int sx, int sy) :x(sx), y(sy) {};
Pos(int sx, int sy,int o) :x(sx), y(sy),order(o) {};
};
class Planet :public Pos{
public:
Planet() { kind = 1; };
Planet(int sx, int sy, int o) :Pos(sx, sy,o) { kind = 1; };
};
class Station :public Pos {
public:
Station() { kind = 2; };
Station(int sx, int sy,int o) :Pos(sx, sy,o) { kind = 2; };
};
int getFuel(Pos& l, Pos& r) {
int dis = (l.x - r.x) * (l.x - r.x) + (l.y - r.y) * (l.y - r.y);
if (l.kind != r.kind)
return dis * A;
if (l.kind == 1)
return dis * A * A;
return dis;
}
V<Planet> planets;
V<Station> stations;
Pos& setPos(int k) {
if (k < N)return planets[k];
return stations[k % N];
}
int getScore(V<int>& route) {
int sumFuel = 0;
FOR(i, 1, route.size() - 1) {
Pos& current = setPos(route[i - 1]);
Pos& target = setPos(route[i]);
sumFuel += getFuel(current, target);
}
return int(round(1000000000.0 / (1000.0 + sqrt(sumFuel))));
}
class State {
public:
int fuel=0;
int counter=0;
V<int> route;
State() {};
State(int f, int c, V<int> r) :fuel(f), counter(c), route(r) {};
};
bool operator < (const State& l, const State& r) {
return l.fuel > r.fuel;
}
class Ship {
public:
V<bool> visited;
int counter = 0;
int last = 0;
int fuel = 0;
Ship(){};
void play(int target) {
if (target < N) {
visited[target] = true;
counter++;
}
Pos& temp = setPos(last);
Pos& next = setPos(target);
fuel += getFuel(temp, next);
last = target;
}
void play(V<int>& route) {
FOR(i, 1, route.size() - 1)
play(route[i]);
}
void back(int target,int prev) {
last = prev;
Pos& temp = setPos(last);
Pos& next = setPos(target);
fuel -= getFuel(temp, next);
if (target < N) {
visited[target] = false;
counter--;
}
}
void back(V<int>& route) {
FORD(i, route.size() - 1, 1)
back(route[i], route[i - 1]);
}
};
Ship ship;
//State beamSearch(State& state, int beam_width, int beam_depth) {
// priority_queue<State> now_beam;
// State best_state;
//
// now_beam.push(state);
// REP(t, beam_depth) {
// priority_queue<State> next_beam;
// REP(i, beam_width) {
// if (now_beam.empty())break;
// //多様性もいつか考える
// State now_state = now_beam.top(); now_beam.pop();
// ship.play(now_state.route);
// if (ship.counter == N - 1) {
// ship.play(0);
// State newState = State(ship.fuel, ship.counter, now_state.route);
// newState.route.push_back(0);
// if (best_state.counter < best_state.counter)best_state.counter;
// ship.back(0);
// }
// else {
//
// }
// /*auto legal_actions = now_state.legalActions();
// for (const auto& action : legal_actions) {
// State next_state = now_state;
// next_state.advance(action);
// next_state.evaluateScore();
// if (t == 0)next_state.first_action_ = action;
// next_beam.push(next_state);
// }*/
// }
//
// now_beam = next_beam;
// if (now_beam.empty())break;
// best_state = now_beam.top();
// }
// return best_state;
//}
V<int> chokudaiSearch(int beam_width) {
int beam_depth = N;
auto beam = V<priority_queue<State>>(beam_depth + 1);
REP(t, beam_depth + 1) {
beam[t] = priority_queue<State>();
}
State initState = State(0, 0, V<int>());
initState.route.push_back(0);
beam[0].push(initState);
while (t_diff < TIME_LIMIT) {
REP(t, beam_depth) {
auto& now_beam = beam[t];
auto& next_beam = beam[t + 1];
//cerr << "[" << t << "]" << now_beam.size() << endl;
//中身が多すぎるときに減らす(多様性は考えていない)
/*int max_load = 100;
if (SZ(now_beam) > max_load) {
priority_queue<State> pool;
REP(i, max_load) {
pool.push(now_beam.top());
now_beam.pop();
}
now_beam.swap(pool);
}*/
REP(i, beam_width) {
if (now_beam.empty())break;
State now_state = now_beam.top();
//cerr << "Yes" << endl;
ship.play(now_state.route);
//if (now_state.isDone()) {
// break;
//}
now_beam.pop();
if (t == N - 1) {
ship.play(0);
now_state.route.push_back(0);
State newState = State(ship.fuel, ship.counter, now_state.route);
next_beam.push(newState);
now_state.route.pop_back();
ship.back(0,now_state.route.back());
}
else {
FOR(npos, 1, N - 1) {
if (ship.visited[npos])continue;
ship.play(npos);
//cerr << "YES" << endl;
now_state.route.push_back(npos);
State newState = State(ship.fuel, ship.counter, now_state.route);
next_beam.push(newState);
now_state.route.pop_back();
ship.back(npos, now_state.route.back());
}
}
ship.back(now_state.route);
//auto legal_actions = now_state.legalActions();
//for (auto& action : legal_actions) {
// State next_state = now_state;
// next_state.advance(action);
// next_state.evaluateScore();
// if (t == 0)next_state.first_action_ = action;
// next_beam.push(next_state);
//}
}
get_time();
if (t_diff > TIME_LIMIT)break;
}
cnt++;
if (t_diff > TIME_LIMIT)break;
//cerr << "Yes" << endl;
}
return beam[N].top().route;
/*FORD(t, beam_depth, 0) {
auto& now_beam = beam[t];
if (!now_beam.empty()) {
return now_beam.top().first_action;
}
}*/
//return -1;
}
void out(V<int>& route) {
REP(i, M) {
cout << stations[i].x << " " << stations[i].y << endl;
}
cout << route.size() << endl;
for(auto p:route) {
Pos& pos = setPos(p);
cout << pos.kind << " " << pos.order << endl;
}
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
t_start = chrono::system_clock::now();
get_time();
cin >> N >> M;
planets = V<Planet>(N);
stations = V<Station>(M);
ship.visited = V<bool>(N);
REP(i, N) {
int x, y; cin >> x >> y;
planets[i] = Planet(x, y,i+1);
}
REP(i, M) {
int x = xs(1001);
int y = xs(1001);
stations[i] = Station(x, y, i + 1);
}
V<int> route;
//REP(i, N)route.push_back(i);
//route.push_back(0);
route = chokudaiSearch(1);
score = getScore(route);
out(route);
get_time();
cerr << "time=" << int(t_diff) << " ms" << endl;
cerr << "score=" << score << endl;
//cerr << "last=" << last_update << endl;
cerr << "cnt=" << cnt << endl;
//cerr << "update=" << update_cnt << endl;
return 0;
}