結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 lud404Qe8lItbFm
|
| 提出日時 | 2023-04-29 20:38:12 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 902 ms / 1,000 ms |
| コード長 | 6,548 bytes |
| コンパイル時間 | 4,774 ms |
| コンパイル使用メモリ | 268,332 KB |
| 実行使用メモリ | 4,372 KB |
| スコア | 6,839,309 |
| 最終ジャッジ日時 | 2023-04-29 20:38:47 |
| 合計ジャッジ時間 | 34,481 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#if !__INCLUDE_LEVEL__
#include __FILE__
// 0以上UINT_MAX(0xffffffff)以下の乱数を整数で返す(xorshift)
static uint32_t random_xor() {
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;
uint32_t t;
t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
// 0以上1未満の乱数を実数で返す
static double random01() {
return (random_xor() + 0.5) * (1.0 / UINT_MAX);
}
ll Euclid2d(ll x1, ll x2, ll y1, ll y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
};
int main() {
int N, M;
cin >> N >> M;
vector Planet(N, vector<int>(2));
REP(i, N) {
cin >> Planet[i][0] >> Planet[i][1];
}
vector<int> Cluster(N);
random_device seed_gen;
mt19937_64 rnd(seed_gen());
uniform_int_distribution<int> Clu_N(0, M - 1);
uniform_int_distribution<int> Clu_N2(0, N - 1);
vector Center(M, vector<int>(2));
REP(i, N) {
Cluster[i] = Clu_N(rnd);
}
auto start_clock = system_clock::now();
const static double START_TEMP = 1500; // 開始時の温度
const static double END_TEMP = 100; // 終了時の温度
const static double END_TIME = 0.9; // 終了時間(秒)
double time = 0.0; // 経過時間(秒)
do {
vector<int> ClusterNum(M, 0);
vector tmp_center(M, vector<int>(2));
REP(i, N) {
tmp_center[Cluster[i]][0] += Planet[i][0];
tmp_center[Cluster[i]][1] += Planet[i][1];
ClusterNum[Cluster[i]] += 1;
}
REP(m, M) {
if (ClusterNum[m] == 0) continue;
tmp_center[m][0] /= ClusterNum[m];
tmp_center[m][1] /= ClusterNum[m];
}
ll nowD = 0;
const double progress_ratio =
time / END_TIME; // 進捗。開始時が0.0、終了時が1.0
const double temp =
START_TEMP + (END_TEMP - START_TEMP) * progress_ratio;
const ll i = Clu_N2(rnd);
int c = Cluster[i];
const ll D = Euclid2d(Planet[i][0], tmp_center[c][0], Planet[i][1],
tmp_center[c][1]);
const ll m = Clu_N(rnd);
const ll tgt_D = Euclid2d(Planet[i][0], tmp_center[m][0], Planet[i][1],
tmp_center[m][1]);
const double probability =
exp((double)(D - tgt_D) / temp); // 焼きなまし法の遷移確率
if (probability > random01()) {
Cluster[i] = m;
Center = move(tmp_center);
}
time = (duration_cast<microseconds>(system_clock::now() - start_clock)
.count() *
1e-6);
} while (time < END_TIME);
REP(m, M) {
cout << Center[m][0] << " " << Center[m][1] << endl;
}
vector<pair<int, int>> Out;
int start = 0;
vector Cplanet(8, vector<int>(0));
REP(i, N) {
Cplanet[Cluster[i]].emplace_back(i);
if (i == 0) start = Cluster[i];
}
Out.emplace_back(1, 1);
Out.emplace_back(2, start + 1);
REP(m, M) {
int station = (m + start) % M;
if (station == start) {
REPE(j, 1, Cplanet[station].size() - 1) {
Out.emplace_back(1, Cplanet[station][j] + 1);
Out.emplace_back(2, station + 1);
}
} else {
REP(j, Cplanet[station].size()) {
Out.emplace_back(1, Cplanet[station][j] + 1);
Out.emplace_back(2, station + 1);
}
}
Out.emplace_back(2, (station + 1) % M + 1);
}
Out.emplace_back(1, 1);
ll V = Out.size();
cout << V << "\n";
REP(v, V) {
cout << Out[v].first << " " << Out[v].second << "\n";
}
}
#else
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace chrono;
using namespace atcoder;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define RREP(i, n) for (ll i = (ll)(n - 1); i >= 0; i--)
#define REPE(i, l, n) for (ll i = l; i <= ll(n); i++)
#define RREPE(i, l, n) for (ll i = ll(n); i >= l; i--)
#define FORA(i, I) for (const auto &i : I)
#define ALL(v) v.begin(), v.end()
#define UQ(v) v.erase(unique(ALL(v)), v.end())
#define ACM(v) accumulate(ALL(v), 0LL)
#define C cin >>
#define P(str) cout << str << endl
#define PLL pair<ll, ll>
#define PDBL pair<double, double>
#define TULL tuple<ll, ll, ll>
#define VPLL vector<PLL>
#define VLL vector<ll>
#define VVLL vector<VLL>
#define VVVLL vector<VVLL>
#define VDBL vector<double>
#define VPDBL vector<PDBL>
#define DLL deque<ll>
#define INCANT cin.tie(nullptr), ios::sync_with_stdio(false)
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
IN(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
IN(name)
#define VEC2(type, name1, name2, size) \
vector<type> name1(size), name2(size); \
for (int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size) \
vector<type> name1(size), name2(size), name3(size); \
for (int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN(name)
template <typename T>
inline bool chmax(T &a, T b) {
return ((a < b) ? (a = b, true) : (false));
}
template <typename T>
inline bool chmin(T &a, T b) {
return ((a > b) ? (a = b, true) : (false));
}
int scan() {
return getchar();
}
void scan(int &a) {
cin >> a;
}
void scan(long long &a) {
cin >> a;
}
void scan(char &a) {
cin >> a;
}
void scan(double &a) {
cin >> a;
}
void scan(string &a) {
cin >> a;
}
template <class T, class S>
void scan(pair<T, S> &p) {
scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T> &);
template <class T>
void scan(vector<T> &a) {
for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
cin >> a;
}
void IN() {
}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
scan(head);
IN(tail...);
}
const long long INF = 1100000000000000000;
const double EPS = 1e-9;
#endif