結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 bond_cmprog
|
| 提出日時 | 2022-07-30 16:59:34 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 992 ms / 1,000 ms |
| コード長 | 12,511 bytes |
| コンパイル時間 | 2,244 ms |
| 実行使用メモリ | 5,160 KB |
| スコア | 7,042,866 |
| 最終ジャッジ日時 | 2022-07-30 17:00:16 |
| 合計ジャッジ時間 | 34,373 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#include <bits/stdc++.h>
#include <sys/time.h>
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#define ALL(v) (v).begin(), (v).end()
#define OVERLOAD4(_1, _2, _3, _4, name, ...) name
#define REP1(n) for(int i=0;i<n;i++)
#define REP2(i, n) for(int i=0;i<n;i++)
#define REP3(i, a, b) for(int i=a;i<b;i++)
#define REP4(i, a, b, c) for(int i=a;i<b;i+=c)
#define REP(...) OVERLOAD4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
//const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll MOD = 1000000007;
const double PI = acos(-1.0);
// const double PI = 2 * acos(0);
constexpr double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/* ----------------------- DEBUG FUNCTION ---------------------------- */
#define DUMPOUT cerr
#define DEBUG_ 1
void dump_function() { DUMPOUT << ' '; }
void dump_function(bool a) { DUMPOUT << a; }
void dump_function(int a) { DUMPOUT << a; }
void dump_function(long long a) { DUMPOUT << a; }
void dump_function(char a) { DUMPOUT << a; }
void dump_function(string &a) { DUMPOUT << a; }
void dump_function(double a) { DUMPOUT << a; }
template <class T> void dump_function(const vector<T> &);
template <class T, size_t size> void dump_function(const array<T, size> &);
template <class T, class L> void dump_function(const pair<T, L> &p);
template <class T, size_t size> void dump_function(const T (&)[size]);
template <class T> void dump_function(const vector<T> &a) {
if(a.empty()) return;
dump_function(a[0]);
for(auto i = a.begin(); ++i != a.end();) {
DUMPOUT << " ";
dump_function(*i);
}
DUMPOUT << endl;
}
template <class T> void dump_function(const deque<T> &a) {
if(a.empty()) return;
dump_function(a[0]);
for(auto i = a.begin(); ++i != a.end();) {
DUMPOUT << " ";
dump_function(*i);
}
}
template <class T, size_t size> void dump_function(const array<T, size> &a) {
dump_function(a[0]);
for(auto i = a.begin(); ++i != a.end();) {
DUMPOUT << " ";
dump_function(*i);
}
}
template <class T, class L> void dump_function(const pair<T, L> &p) {
DUMPOUT << '(';
dump_function(p.first);
DUMPOUT << ",";
dump_function(p.second);
DUMPOUT << ')';
}
template <class T> void dump_function(set<T> &x) {
for(auto e : x) dump_function(e), DUMPOUT << " ";
DUMPOUT << endl;
}
template <class T> void dump_function(multiset<T> &x) {
for(auto e : x) dump_function(e), DUMPOUT << " ";
DUMPOUT << endl;
}
template <class T, size_t size> void dump_function(const T (&a)[size]) {
dump_function(a[0]);
for(auto i = a; ++i != end(a);) {
DUMPOUT << " ";
dump_function(*i);
}
}
template <class T> void dump_function(const T &a) { DUMPOUT << a; }
int dump_out() {
DUMPOUT << '\n';
return 0;
}
template <class T> int dump_out(const T &t) {
dump_function(t);
DUMPOUT << '\n';
return 0;
}
template <class Head, class... Tail> int dump_out(const Head &head, const Tail &... tail) {
dump_function(head);
DUMPOUT << ' ';
dump_out(tail...);
return 0;
}
#ifdef DEBUG_
#define dump(x) \
DUMPOUT << #x << ": "; \
dump_function(x); \
DUMPOUT << endl;
void dumps() {}
template <class T> void dumps(const T &t) {
dump_function(t);
DUMPOUT << " ";
}
template <class Head, class... Tail> void dumps(const Head &head, const Tail &... tail) {
dump_function(head);
DUMPOUT << ' ';
dump_out(tail...);
}
#else
#define dump(x)
template <class... T> void dumps(const T &...) {}
#endif
/* ----------------------- DEBUG FUNCTION ---------------------------- */
constexpr ll CYCLES_PER_SEC = 2800000000;
constexpr double TL = 990;
double get_ms() { struct timeval t; gettimeofday(&t, NULL); return (double)t.tv_sec * 1000 + (double)t.tv_usec / 1000; }
uint32_t XorShift(void) {
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));
}
double Prob(void){
double ret = (double)XorShift() / UINT_MAX;
return ret;
}
struct RNG {
unsigned int MT[624];
int index;
RNG(int seed = 1) {init(seed);}
void init(int seed = 1) {MT[0] = seed; REP(i, 1, 624) MT[i] = (1812433253UL * (MT[i-1] ^ (MT[i-1] >> 30)) + i); index = 0; }
void generate() {
const unsigned int MULT[] = {0, 2567483615UL};
REP(i, 227) {unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL); MT[i] = MT[i+397] ^ (y >> 1); MT[i] ^= MULT[y&1]; }
REP(i, 227, 623) {unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL); MT[i] = MT[i-227] ^ (y >> 1); MT[i] ^= MULT[y&1]; }
unsigned int y = (MT[623] & 0x8000000UL) + (MT[0] & 0x7FFFFFFFUL); MT[623] = MT[623-227] ^ (y >> 1); MT[623] ^= MULT[y&1];
}
unsigned int rand() { if (index == 0) generate(); unsigned int y = MT[index]; y ^= y >> 11; y ^= y << 7 & 2636928640UL; y ^= y << 15 & 4022730752UL; y ^= y >> 18; index = index == 623 ? 0 : index + 1; return y;}
inline __attribute__ ((always_inline)) int next() {return rand(); }
inline __attribute__ ((always_inline)) int next(int x) {return rand() % x; }
inline __attribute__ ((always_inline)) int next(int a, int b) {return a + (rand() % (b - a)); }
inline __attribute__ ((always_inline)) double next_double() {return (rand() + 0.5) * (1.0 / 4294967296.0); }
inline __attribute__ ((always_inline)) double next_double(double a, double b) {return a + next_double() * (b - a); }
};
static RNG rng;
const int N = 100;
const int M = 8;
const int alpha = 5;
vector<int> a(N), b(N);
vector<int> c(M), d(M);
vector<int> ans;
vector<vector<int>> dist(N, vector<int>(N));
double start = 0.0;
vector<int> labels(N);
vector<int> clusters(M); // cluster[i]に含まれる点の個数
namespace yukicoder_score_contest2{
void init(){
REP(i,N) ans.emplace_back(i);
// calc_dist
REP(i,N) REP(j,N) dist[i][j] = alpha * alpha * ((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
}
void input(){
int _N, _M;
cin >> _N >> _M;
start = get_ms();
REP(i,N) cin >> a[i] >> b[i];
}
void output() {
// REP(i,M) cout << c[i] << " " << d[i] << "\n";
int idx1 = 0;
int sz = ans.size();
cout << sz+1 << endl;
REP(i,sz) if(ans[i] == 0) idx1 = i;
REP(i,sz) {
if(ans[(idx1+i)%sz] >= N) cout << "2 " << ans[(idx1+i)%sz] - N + 1 << "\n";
else cout << "1 " << ans[(idx1+i)%sz] + 1 << "\n";
}
cout << "1 " << ans[idx1] + 1 << endl;
}
int calc_diff(int i0, int i1) {
int j0 = (i0 + N - 1) % N;
int j1 = (i1 + 1) % N;
const double d_cur = dist[ans[i0]][ans[j0]] + dist[ans[i1]][ans[j1]];
const double d_next = dist[ans[i0]][ans[j1]] + dist[ans[i1]][ans[j0]];
return d_cur - d_next;
}
void k_means() {
REP(i,N) labels[i] = i % M;
const int MAX_ITER = 1000;
int iter = 0;
bool update = true;
while(iter < MAX_ITER and update) {
update = false;
REP(i,M) c[i] = d[i] = clusters[i] = 0;
REP(i,N) {
int label = labels[i];
c[label] += a[i];
d[label] += b[i];
clusters[label]++;
}
REP(i,M) if(clusters[i] > 0) c[i] /= clusters[i], d[i] /= clusters[i];
REP(i,N) {
int mi = INF;
int new_cluster = labels[i];
REP(j,M) if(chmin(mi, (a[i] - c[j]) * (a[i] - c[j]) + (b[i] - b[j]) * (b[i] - b[j]))) new_cluster = j;
if(labels[i] != new_cluster) {
update = true;
labels[i] = new_cluster;
}
}
iter++;
}
dump(clusters);
dump(iter);
}
void output_k_means() {
REP(i,M) cout << c[i] << " " << d[i] << endl;
}
void SA(){
int iter = 0;
int move = 0;
int last_move = 0;
const double T_init = 260;
const double T_end = 50;
double T = 100;
for(iter = 1 ; ; iter++) {
int i0 = rng.next(N);
int i1 = rng.next(N);
if(i0 > i1) swap(i0, i1);
const int diff = calc_diff(i0, i1);
if(diff > 0 or exp(diff / T) > (double)rng.next(INF+9)) {
reverse(ans.begin() + i0, ans.begin() + i1 + 1);
move++;
last_move = iter;
}
if(iter % 1000 == 0) {
double elapsed = get_ms() - start;
if(elapsed > TL) break;
T = (T_end - T_init) / TL * elapsed + T_init;
}
}
dump(iter);
dump(move);
dump(last_move);
}
void greedy() {
// dump(ans);
// REP(i,M) {
// int ma = 0;
// int idx = -1;
// int sz = ans.size();
// int best_mx = -1;
// int best_my = -1;
// dump(sz);
// REP(j,sz) {
// int i0 = ans[j];
// int i1 = ans[(j+1)%sz];
// int x_i0 = (i0 >= N ? c[i0 - N] : a[i0]);
// int y_i0 = (i0 >= N ? d[i0 - N] : b[i0]);
// int x_i1 = (i1 >= N ? c[i1 - N] : a[i1]);
// int y_i1 = (i1 >= N ? d[i1 - N] : b[i1]);
// int mx = (x_i0 + x_i1) / 2;
// int my = (y_i0 + y_i1) / 2;
// int d_cur = (x_i0 - x_i1) * (x_i0 - x_i1) + (y_i0 - y_i1) * (y_i0 - y_i1);
// if(i0 < N) d_cur *= alpha;
// if(i1 < N) d_cur *= alpha;
// int d_next = (i0 < N ? alpha : 1) * ((x_i0 - mx) * (x_i0 - mx) + (y_i0 - my) * (y_i0 - my));
// d_next += (i1 < N ? alpha : 1) * ((x_i1 - mx) * (x_i1 - mx) + (y_i1 - my) * (y_i1 - my));
// if(chmax(ma, d_cur - d_next)) {
// idx = j;
// best_mx = mx;
// best_my = my;
// }
// }
// if(idx) {
// ans.insert(ans.begin() + idx + 1, i + N);
// c[i] = best_mx;
// d[i] = best_my;
// }
// }
REP(j,ans.size()) {
int i0 = ans[j];
int i1 = ans[(j+1)%(int)ans.size()];
if(i0 >= N or i1 >= N) continue;
if(labels[i0] != labels[i1]) continue;
int x_i0 = (i0 >= N ? c[i0 - N] : a[i0]);
int y_i0 = (i0 >= N ? d[i0 - N] : b[i0]);
int x_i1 = (i1 >= N ? c[i1 - N] : a[i1]);
int y_i1 = (i1 >= N ? d[i1 - N] : b[i1]);
int mx = c[labels[i0]];
int my = d[labels[i0]];
int d_cur = (x_i0 - x_i1) * (x_i0 - x_i1) + (y_i0 - y_i1) * (y_i0 - y_i1);
if(i0 < N) d_cur *= alpha;
if(i1 < N) d_cur *= alpha;
int d_next = (i0 < N ? alpha : 1) * ((x_i0 - mx) * (x_i0 - mx) + (y_i0 - my) * (y_i0 - my));
d_next += (i1 < N ? alpha : 1) * ((x_i1 - mx) * (x_i1 - mx) + (y_i1 - my) * (y_i1 - my));
if(d_cur - d_next > 0) {
ans.insert(ans.begin() + j + 1, labels[i0] + N);
j++;
}
}
}
void main(){
input();
init();
k_means();
output_k_means();
SA();
greedy();
output();
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
yukicoder_score_contest2::main();
}