結果

問題 No.5007 Steiner Space Travel
ユーザー highjumphighjump
提出日時 2022-07-30 15:05:18
言語 C++17
(gcc 12.3.0 + boost 1.83.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
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,900 KB
testcase_01 AC 2 ms
5,160 KB
testcase_02 AC 2 ms
4,900 KB
testcase_03 AC 1 ms
5,156 KB
testcase_04 AC 2 ms
4,904 KB
testcase_05 AC 1 ms
3,480 KB
testcase_06 AC 1 ms
4,908 KB
testcase_07 AC 2 ms
5,156 KB
testcase_08 AC 2 ms
5,160 KB
testcase_09 AC 1 ms
4,904 KB
testcase_10 AC 2 ms
5,160 KB
testcase_11 AC 2 ms
4,900 KB
testcase_12 AC 2 ms
4,904 KB
testcase_13 AC 1 ms
4,900 KB
testcase_14 AC 2 ms
4,904 KB
testcase_15 AC 2 ms
4,904 KB
testcase_16 AC 1 ms
4,908 KB
testcase_17 AC 2 ms
4,904 KB
testcase_18 AC 2 ms
4,904 KB
testcase_19 AC 2 ms
5,156 KB
testcase_20 AC 2 ms
4,900 KB
testcase_21 AC 1 ms
4,904 KB
testcase_22 AC 2 ms
5,160 KB
testcase_23 AC 2 ms
4,900 KB
testcase_24 AC 1 ms
4,900 KB
testcase_25 AC 2 ms
4,900 KB
testcase_26 AC 2 ms
4,900 KB
testcase_27 AC 1 ms
3,356 KB
testcase_28 AC 2 ms
3,496 KB
testcase_29 AC 2 ms
3,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0