結果

問題 No.5007 Steiner Space Travel
ユーザー unsre
提出日時 2022-07-30 14:57:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 955 ms / 1,000 ms
コード長 7,586 bytes
コンパイル時間 1,328 ms
実行使用メモリ 4,064 KB
スコア 6,846,324
最終ジャッジ日時 2022-07-30 14:58:22
合計ジャッジ時間 32,567 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

#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.95;
#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;
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) {
REP(i,0,m) {
c[i] = xor96() % 1001;
d[i] = xor96() % 1001;
}
}
void init(int n, const VI &a, const VI &b) {
score = calcScore(n,a,b);
}
LL calcScore(int n, const VI &a, const VI &b) {
LL score = 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(a[idx],b[idx],a[i],b[i]))) {
dst = i;
}
}
if (dst > -1) idx = dst;
}
score += calcShortest(a[idx],b[idx],a[0],b[0]);
return score;
}
State modify(int n, const VI &a, const VI &b) {
//
int r = xor96() % 2;
int idx = xor96() % m;
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(a[idx],b[idx],a[i],b[i]))) {
dst = i;
}
}
if (dst > -1) idx = dst;
}
path.push_back(0);
VP ps = {{1,0}};
REP(i,1,path.size()) {
int sx = a[path[i-1]], sy = b[path[i-1]];
int tx = a[path[i]], ty = b[path[i]];
int mid = -1;
long long ret = 1LL * (sqr(sx-tx) + sqr(sy-ty)) * sqr(alpha);
REP(i,0,m) {
int mx = c[i], my = d[i];
if (chmin(ret, 1LL * (sqr(sx-mx) + sqr(sy-my) + sqr(tx-mx) + sqr(ty-my)) * alpha)) {
mid = i;
}
}
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 sx, int sy, int tx, int ty) {
long long ret = 1LL * (sqr(sx-tx) + sqr(sy-ty)) * sqr(alpha);
REP(i,0,m) {
int mx = c[i], my = d[i];
chmin(ret, 1LL * (sqr(sx-mx) + sqr(sy-my) + sqr(tx-mx) + sqr(ty-my)) * alpha);
}
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));
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));
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0