結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 unsre
|
| 提出日時 | 2022-07-30 15:38:37 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 980 ms / 1,000 ms |
| コード長 | 8,095 bytes |
| コンパイル時間 | 1,883 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 6,209,711 |
| 最終ジャッジ日時 | 2022-07-30 15:39:11 |
| 合計ジャッジ時間 | 34,058 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 979 ms
6,948 KB |
| testcase_01 | AC | 978 ms
6,948 KB |
| testcase_02 | AC | 978 ms
4,904 KB |
| testcase_03 | AC | 979 ms
4,900 KB |
| testcase_04 | AC | 979 ms
4,904 KB |
| testcase_05 | AC | 978 ms
4,904 KB |
| testcase_06 | AC | 979 ms
4,900 KB |
| testcase_07 | AC | 979 ms
4,900 KB |
| testcase_08 | AC | 978 ms
6,948 KB |
| testcase_09 | AC | 977 ms
4,908 KB |
| testcase_10 | AC | 979 ms
6,948 KB |
| testcase_11 | AC | 980 ms
4,900 KB |
| testcase_12 | AC | 977 ms
4,904 KB |
| testcase_13 | AC | 978 ms
4,904 KB |
| testcase_14 | AC | 978 ms
4,904 KB |
| testcase_15 | AC | 978 ms
4,900 KB |
| testcase_16 | AC | 979 ms
4,904 KB |
| testcase_17 | AC | 978 ms
4,900 KB |
| testcase_18 | AC | 979 ms
4,908 KB |
| testcase_19 | AC | 978 ms
4,904 KB |
| testcase_20 | AC | 977 ms
6,952 KB |
| testcase_21 | AC | 979 ms
6,948 KB |
| testcase_22 | AC | 980 ms
4,900 KB |
| testcase_23 | AC | 979 ms
4,904 KB |
| testcase_24 | AC | 978 ms
4,908 KB |
| testcase_25 | AC | 978 ms
6,948 KB |
| testcase_26 | AC | 979 ms
4,908 KB |
| testcase_27 | AC | 978 ms
4,904 KB |
| testcase_28 | AC | 978 ms
4,904 KB |
| testcase_29 | AC | 979 ms
4,904 KB |
ソースコード
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>
#include <limits>
#include <chrono>
#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long
#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x) cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR
#endif
using namespace std;
using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
template<class T> using V = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
//constexpr double EPS = 1e-10;
//constexpr double PI = acos(-1.0);
//constexpr int INF = INT_MAX;
//constexpr int INF = numeric_limits<int>::max()/2;
//constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}
template<class T> inline T sqr(T x) {return x*x;}
long double sqrt(int v) {return sqrt((long double)v);}
long double sqrt(long long v) {return sqrt((long double)v);}
constexpr double baseTimeLimit = 0.975;
#ifdef LOCAL
constexpr int timemul = 1;
#else
constexpr int timemul = 1;
#endif
constexpr double timeLimit = baseTimeLimit * timemul;
constexpr int alpha = 5;
double diff(const chrono::system_clock::time_point &st) {
return chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now() - st).count() * 1e-6;
}
unsigned int xor96(void) {
static unsigned int x = 123456789;
static unsigned int y = 362436069;
static unsigned int z = 521288629;
unsigned int t;
t = (x ^ (x << 3)) ^ (y ^ (y >> 19)) ^ (z ^ (z << 6));
x = y; y = z;
return z = t;
}
class State {
public:
LL score;
// VLL scores;
int m;
VI c,d;
VI usedCnt;
VVLL pd;
VVLL sd;
State(const State&) = default;
State(State&&) = default;
State& operator=(const State&) = default;
State& operator=(State&&) = default;
State(int m): score(0), m(m), c(m), d(m), usedCnt(m) {
REP(i,0,m) {
c[i] = xor96() % 1001;
d[i] = xor96() % 1001;
}
}
void init(int n, const VI &a, const VI &b) {
pd = VVLL(n,VLL(n));
sd = VVLL(m,VLL(n));
REP(i,0,n) REP(j,i,n) {
pd[i][j] = pd[j][i] = 1LL * (sqr(a[i]-a[j]) + sqr(b[i]-b[j])) * sqr(alpha);
}
REP(i,0,m) REP(j,0,n) {
sd[i][j] = 1LL * (sqr(c[i]-a[j]) + sqr(d[i]-b[j])) * sqr(alpha);
}
score = calcScore(n,a,b);
}
LL calcScore(int n, const VI &a, const VI &b) {
LL score = 0;
REP(i,0,m) usedCnt[i] = 0;
VI visited(n);
int idx = 0, cnt = 0;
while (cnt < n) {
++cnt;
visited[idx] = true;
int dst = -1;
LL d = 1LL<<60;
REP(i,0,n) {
if (visited[i]) continue;
if (chmin(d, calcShortest(idx,i))) {
dst = i;
}
}
if (dst > -1) idx = dst;
}
score += calcShortest(idx,0);
return score;
}
State modify(int n, const VI &a, const VI &b) {
// 選択・分岐処理
int r = xor96() % 2;
int idx = xor96() % m;
VI unused;
REP(i,0,m) if (usedCnt[i] == 0) unused.push_back(i);
if (!unused.empty()) {
idx = unused[xor96()%unused.size()];
}
State newState(*this);
if (r % 2) newState.modifyX(n,a,b,idx);
else newState.modifyY(n,a,b,idx);
return newState;
}
void print(int n, const VI &a, const VI &b) {
REP(i,0,m) {
cout << c[i] << " " << d[i] << endl;
}
VI visited(n);
int idx = 0, cnt = 0;
VI path;
while (cnt < n) {
++cnt;
visited[idx] = true;
path.push_back(idx);
int dst = -1;
LL d = 1LL<<60;
REP(i,0,n) {
if (visited[i]) continue;
if (chmin(d, calcShortest(idx,i))) {
dst = i;
}
}
if (dst > -1) idx = dst;
}
path.push_back(0);
VP ps = {{1,0}};
REP(i,1,path.size()) {
int mid = -1;
long long ret = pd[path[i-1]][path[i]];
REP(j,0,m) {
if (chmin(ret, sd[j][path[i-1]] + sd[j][path[i]])) {
mid = j;
}
}
if (mid > -1) {
ps.pb(2,mid);
}
ps.pb(1,path[i]);
}
cout << ps.size() << endl;
for (auto [t,r]: ps) {
cout << t << " " << r + 1 << endl;
}
}
private:
long long calcShortest(int s, int t) {
long long ret = pd[s][t];
int mid = -1;
REP(i,0,m) {
if (chmin(ret, sd[i][s] + sd[i][t])) {
mid = i;
}
}
if (mid > -1) usedCnt[mid]++;
return ret;
}
void modifyX(int n, const VI &a, const VI &b, int idx) {
int dist = xor96() % 1000 - 500;
c[idx] = max(0,min(1000,c[idx]+dist));
REP(j,0,n) {
sd[idx][j] = 1LL * (sqr(c[idx]-a[j]) + sqr(d[idx]-b[j])) * sqr(alpha);
}
score = calcScore(n,a,b);
}
void modifyY(int n, const VI &a, const VI &b, int idx) {
int dist = xor96() % 1000 - 500;
d[idx] = max(0,min(1000,d[idx]+dist));
REP(j,0,n) {
sd[idx][j] = 1LL * (sqr(c[idx]-a[j]) + sqr(d[idx]-b[j])) * sqr(alpha);
}
score = calcScore(n,a,b);
}
};
// 焼きなまし法
State sa(int n, int m, const VI &a, const VI &b, double start_temp, double end_temp, double TIME_LIMIT) {
State state(m);
state.init(n,a,b);
//int times = 0;
chrono::system_clock::time_point st = chrono::system_clock::now();
int cnt = 0;
double dt;
while ((dt = diff(st)) < TIME_LIMIT) { // 時間の許す限り回す
REP(loop,0,10) {
State new_state = state.modify(n,a,b);
int new_score = new_state.score;
int pre_score = state.score;
// 温度関数
double temp = start_temp + (end_temp - start_temp) * dt / TIME_LIMIT;
// 遷移確率関数
double prob = exp(-((double)(new_score-pre_score))/temp); // 最小値
// double prob = exp(((double)(new_score-pre_score))/temp); // 最大値
if (prob > (xor96()%0xffffffffu)/(double)0xffffffffu) { // 確率probで遷移する
state = new_state;
}
}
++cnt;
dump(state.score);
}
dump(cnt);
return state;
}
void solve() {
auto st = chrono::system_clock::now();
int r = random_device()() % 1000;
REP(i,0,r) xor96();
int n,m;
cin >> n >> m;
VI a(n),b(n);
REP(i,0,n) cin >> a[i] >> b[i];
int times = 2;
auto state = sa(n,m,a,b,1000,100,timeLimit/times);
REP(i,1,times) {
auto state2 = sa(n,m,a,b,1000,100,timeLimit/times);
if (state2.score < state.score) {
state = move(state2);
}
}
dump(state.score);
state.print(n,a,b);
}
signed main() {
int t = 1;
// cin >> t;
REP(i,0,t) {
solve();
}
return 0;
}