結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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#endifusing 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 LOCALconstexpr int timemul = 1;#elseconstexpr int timemul = 1;#endifconstexpr 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;}