結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 15:05:18 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 4,691 bytes |
コンパイル時間 | 1,488 ms |
実行使用メモリ | 5,160 KB |
スコア | 1,221,702 |
最終ジャッジ日時 | 2022-07-30 15:05:21 |
合計ジャッジ時間 | 3,377 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#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 = 2930;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;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 fuel(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;V<bool> visited;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 += fuel(current, target);}return int(round(1000000000.0 / (1000.0 + sqrt(sumFuel))));}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);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);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;}