結果

問題 No.5007 Steiner Space Travel
ユーザー eijirou
提出日時 2022-07-30 15:40:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 7,335 bytes
コンパイル時間 3,948 ms
実行使用メモリ 6,952 KB
スコア 6,951,051
最終ジャッジ日時 2022-07-30 15:40:52
合計ジャッジ時間 5,780 ms
ジャッジサーバーID
(参考情報)
judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
template <class T>
T sum(vector<T>& array) {
return accumulate(array.begin(), array.end(), (T)0);
}
template <class T>
int index(vector<T>& data, T element) {
return distance(data.begin(), find(data.begin(),data.end(),element));
}
template <class T>
int contain(vector<T>& data, T element) {
return !(index(data, element) == (int)data.size());
}
struct Randomizer {
mt19937_64 engine;
uniform_int_distribution<> dist = uniform_int_distribution<>(0, INT_MAX);
Randomizer() {
random_device seed_gen;
engine = mt19937_64(seed_gen());
}
Randomizer(int seed) {
engine = mt19937_64(seed);
}
double uniform(double l, double r) {
assert(l <= r);
return l + (r-l)*dist(engine)/INT_MAX;
}
int randrange(int l, int r) {
assert(l < r);
return l + dist(engine)%(r-l);
}
template <class T>
T choice(vector<T>& data) {
return data.at(randrange(0, data.size()));
}
vector<int> sample(int l, int r, int num) {
assert(0 < num && num <= r - l);
vector<int> ret;
while ((int)ret.size() < num) {
int x = randrange(l, r);
if (!contain(ret, x)) {
ret.push_back(x);
}
}
sort(ret.begin(), ret.end());
return ret;
}
};
struct Timer {
timespec start;
Randomizer randomizer;
Timer() {}
Timer(int seed) {
randomizer = Randomizer(seed);
}
void begin() {
clock_gettime(CLOCK_REALTIME, &start);
}
double stopwatch() {
timespec end;
clock_gettime(CLOCK_REALTIME, &end);
double sec = end.tv_sec - start.tv_sec;
double nsec = end.tv_nsec - start.tv_nsec;
return sec + nsec/1000000000;
}
bool scheduler(double delta, double time_limit, double t0, double t1) {
assert(0.0 < time_limit && 0.0 <= t1 && t1 <= t0);
if (0.0 <= delta) {
return true;
} else {
double ratio = stopwatch() / time_limit;
double t = pow(t0, 1.0-ratio) * pow(t1, ratio);
return randomizer.uniform(0.0, 1.0) < pow(2.0, delta/t);
}
}
};
vector<int> tsp_solver(vector<vector<int>> cost_matrix) {
// n TSP.
int n = cost_matrix.size() - 1;
int s = n;
int inf = 1 << 30;
// dp
vector<vector<int>> dp(n, vector<int>(1<<n,inf));
for (int i = 0; i < n; i++) {
dp[i][1<<i] = cost_matrix[s][i];
}
for (int mask = 1; mask < 1<<n; mask++) {
for (int i = 0; i < n; i++) {
if ((mask>>i & 1) == 0) {
continue;
}
for (int j = 0; j < n; j++) {
if (mask>>j & 1) {
continue;
}
dp[j][mask^(1<<j)] = min(dp[j][mask^(1<<j)], dp[i][mask]+cost_matrix[i][j]);
}
}
}
//
int last = 0;
int cost = inf;
for (int i = 0; i < n; i++) {
if (dp[i].back() + cost_matrix[i][s] < cost) {
last = i;
cost = dp[i].back() + cost_matrix[i][s];
}
}
vector<int> ret = {last};
int mask = (1<<n) - 1;
mask ^= 1 << last;
while (mask) {
int j = ret.back();
for (int i = 0; i < n; i++) {
if (mask>>i & 1 && dp[i][mask] + cost_matrix[i][j] == dp[j][mask^1<<j]) {
ret.push_back(i);
mask ^= 1 << i;
break;
}
}
assert(ret.back() != j);
}
ret.push_back(s);
reverse(ret.begin(), ret.end());
return ret;
}
const int alpha = 5;
const double time_limit = 0.95;
const int inf = 1 << 30;
struct Solver {
Timer timer;
Randomizer randomizer;
int n, m;
vector<int> a, b;
vector<vector<int>> groups;
vector<int> c, d;
Solver() {
timer.begin();
}
void input() {
cin >> n >> m;
a = vector<int>(n);
b = vector<int>(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
}
pair<int,int> get_center(vector<int>& group) {
if (group.empty()) {
int j = randomizer.randrange(0, n);
return {a[j], b[j]};
}
int x = 0;
int y = 0;
for (int i : group) {
x += a[i];
y += b[i];
}
return {x/(int)group.size(), y/(int)group.size()};
}
void k_means() {
groups = vector<vector<int>>(m);
for (int i = 0; i < m; i++) {
groups[i].push_back(i);
}
for (int i = m; i < n; i++) {
groups[randomizer.randrange(0,m)].push_back(i);
}
while (true) {
vector<pair<int,int>> centers(m);
for (int i = 0; i < m; i++) {
centers[i] = get_center(groups[i]);
}
vector<vector<int>> new_groups(m);
for (int i = 0; i < n; i++) {
int best = 0;
int min_cost = inf;
for (int j = 0; j < m; j++) {
auto [x, y] = centers[j];
int cost = (a[i]-x)*(a[i]-x) + (b[i]-y)*(b[i]-y);
if (cost < min_cost) {
best = j;
min_cost = cost;
}
}
new_groups[best].push_back(i);
}
if (groups == new_groups) {
break;
}
groups = new_groups;
}
}
void solve() {
k_means();
c = vector<int>(m);
d = vector<int>(m);
for (int i = 0; i < m; i++) {
pair<int,int> p = get_center(groups[i]);
c[i] = p.first;
d[i] = p.second;
}
vector<vector<int>> cost_matrix(m, vector<int>(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
int dist = (c[i]-c[j])*(c[i]-c[j]) + (d[i]-d[j])*(d[i]-d[j]);
cost_matrix[i][j] = dist;
cost_matrix[j][i] = dist;
}
}
vector<int> order = tsp_solver(cost_matrix);
int start = -1;
for (int i = 0; i < m; i++) {
if (contain(groups[order[i]], 0)) {
start = i;
}
}
vector<int> new_order(m);
for (int i = 0; i < m; i++) {
new_order[i] = order[(start+i) % m];
}
order = new_order;
for (int i = 0; i < m; i++) {
cout << c[i] << ' ' << d[i] << '\n';
}
cout << 2*n + m + 1 << '\n';
for (int i = 0; i < m; i++) {
int station = order[i];
for (int star : groups[station]) {
cout << 1 << ' ' << star + 1 << '\n';
cout << 2 << ' ' << station + 1 << '\n';
}
cout << 2 << ' ' << order[(i+1) % m] + 1 << '\n';
}
cout << 1 << ' ' << 1 << '\n';
}
};
int main() {
Solver solver;
solver.input();
solver.solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0