結果
問題 | No.5007 Steiner Space Travel |
ユーザー | Kahuka |
提出日時 | 2023-04-23 13:40:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 934 ms / 1,000 ms |
コード長 | 8,162 bytes |
コンパイル時間 | 3,025 ms |
コンパイル使用メモリ | 210,212 KB |
実行使用メモリ | 4,372 KB |
スコア | 8,876,944 |
最終ジャッジ日時 | 2023-04-23 13:41:25 |
合計ジャッジ時間 | 34,403 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 932 ms
4,368 KB |
testcase_01 | AC | 907 ms
4,372 KB |
testcase_02 | AC | 932 ms
4,372 KB |
testcase_03 | AC | 932 ms
4,372 KB |
testcase_04 | AC | 907 ms
4,372 KB |
testcase_05 | AC | 907 ms
4,372 KB |
testcase_06 | AC | 933 ms
4,372 KB |
testcase_07 | AC | 907 ms
4,368 KB |
testcase_08 | AC | 934 ms
4,372 KB |
testcase_09 | AC | 934 ms
4,372 KB |
testcase_10 | AC | 913 ms
4,372 KB |
testcase_11 | AC | 907 ms
4,372 KB |
testcase_12 | AC | 932 ms
4,368 KB |
testcase_13 | AC | 934 ms
4,368 KB |
testcase_14 | AC | 933 ms
4,368 KB |
testcase_15 | AC | 932 ms
4,368 KB |
testcase_16 | AC | 933 ms
4,368 KB |
testcase_17 | AC | 907 ms
4,368 KB |
testcase_18 | AC | 908 ms
4,368 KB |
testcase_19 | AC | 933 ms
4,372 KB |
testcase_20 | AC | 906 ms
4,368 KB |
testcase_21 | AC | 907 ms
4,368 KB |
testcase_22 | AC | 933 ms
4,372 KB |
testcase_23 | AC | 933 ms
4,372 KB |
testcase_24 | AC | 908 ms
4,372 KB |
testcase_25 | AC | 908 ms
4,372 KB |
testcase_26 | AC | 911 ms
4,372 KB |
testcase_27 | AC | 933 ms
4,372 KB |
testcase_28 | AC | 932 ms
4,368 KB |
testcase_29 | AC | 907 ms
4,368 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0; i<n; i++) #define reps(i,s,n) for(int i=s; i<n; i++) #define per(i,n) for(int i=n-1; i>=0; i--) #define pers(i,n,s) for(int i=n-1; i>=s; i--) #define all(v) v.begin(),v.end() #define fi first #define se second #define pb push_back #define si(v) int(v.size()) #define lb(v,n) lower_bound(all(v),n) #define lbi(v,n) int(lower_bound(all(v),n) - v.begin()) #define ub(v,n) upper_bound(all(v),n) #define ubi(v,n) int(upper_bound(all(v),n) - v.begin()) #define mod 1000000007 #define infi 1010000000 #define infl 1100000000000000000 #define outve(v) {for(auto i : v) cout << i << " ";cout << endl;} #define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;} #define errve(v) {for(auto i : v) cout << i << " ";cout << endl;} #define errmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;} #define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];} #define IN(n,m,v) rep(i,n) rep(j,m){cin >> v[i][j];} #define cyes cout << "Yes" << endl #define cno cout << "No" << endl #define cYES cout << "YES" << endl #define cNO cout << "NO" << endl #define csp << " " << #define outset(n) cout << fixed << setprecision(n); using namespace std; using ll = long long; using ull = unsigned long long; using uint = unsigned int; using ld = long double; using vi = vector<int>; using vvi = vector<vector<int>>; using vd = vector<double>; using vvd = vector<vector<double>>; using vl = vector<ll>; using vvl = vector<vector<ll>>; using vs = vector<string>; using pii = pair<int,int>; using pll = pair<ll,ll>; template<typename T> using ve = vector<T>; template<typename T> using vv = vector<vector<T>>; template<typename T> using pq2 = priority_queue<T>; template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>; template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;} template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;} int popcnt(uint n) {return __builtin_popcount(n);} int popcntl(ull n) {return __builtin_popcountll(n);} int bsr(uint n) {return 31 - __builtin_clz(n);} int bsrl(ull n) {return 63 - __builtin_clzll(n);} int bsf(uint n) {return __builtin_ctz(n);} int bsfl(ull n) {return __builtin_ctzll(n);} double TIME_LIMIT = 0.9; int LOCAL = 0; int TEATER = 0; unsigned int xorshift() { static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123; unsigned int tt = (tx^(tx<<11)); tx = ty; ty = tz; tz = tw; return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) ); } class Timer { int ti; double time; public: Timer(){} void start(){ti = clock();} inline double get_time(){return time = (LOCAL==1 ? 2.0 : 1.0) * (clock() - ti) / CLOCKS_PER_SEC;} inline double now(){return time;} }; const int N = 100; const int M = 8; const int L = 1001; class SimulatedAnnealing { Timer timer; ll score; int planet_x[N]; int planet_y[N]; int station_x[M]; int station_y[M]; vi order; int alpha = 5; public: SimulatedAnnealing(){ timer.start(); int n,m; cin >> n >> m; rep(i,N) cin >> planet_x[i] >> planet_y[i]; rep(i,M) station_x[i] = xorshift()%L, station_y[i] = xorshift()%L; score = 0; } ll cal_score(vi &ord){ ll res = 0; rep(i,si(order)-1) res += cal_dist(ord[i],ord[i+1]); return 1000000000ll/(1000ll+(ll)sqrt(res)); } ll cal_dist(int a, int b){ int c = 0; int dx = 0, dy = 0; if(a >= N) a -= N, dx = station_x[a], dy = station_y[a]; else c++, dx = planet_x[a], dy = planet_y[a]; if(b >= N) b -= N, dx -= station_x[b], dy -= station_y[b]; else c++, dx -= planet_x[b], dy -= planet_y[b]; int aa = 1; rep(i,c) aa *= alpha; return ll(aa*(dx*dx+dy*dy)); } void solve(){ vi vis(N+M,0); vis[0] = 1; order.pb(0); rep(i,N+M){ int id = -1; ll d = infl; rep(j,N+M) if(vis[j] == 0 && order.back() != j){ if(chmin(d,cal_dist(order.back(),j))) id = j; } if(id == -1) break; order.pb(id); vis[id] = 1; } order.pb(0); score = cal_score(order); cerr << score<< endl; int loop = 0; double T1 = 600, T0 = 0; double T = T1; while (timer.now() < TIME_LIMIT) { loop++; ll score0 = score; vi order0; int station_x0[M],station_y0[M]; int type = 0; int prob = xorshift()%100; if(prob < 6){ type = 0; order0 = order; int n = xorshift()%((si(order))-2)+1; int m = xorshift()%((si(order))-2)+1; while (n == m) m = xorshift()%((si(order))-2)+1; if(n > m) swap(n,m); while (n < m) { swap(order[n],order[m]); n++, m--; } reps(a,1,si(order)-1) reps(b,a+1,si(order)-1){ if(cal_dist(order[a-1],order[a])+cal_dist(order[b],order[b+1]) > cal_dist(order[a-1],order[b])+cal_dist(order[a],order[b+1])){ int n = a, m = b; while (n < m) { swap(order[n],order[m]); n++,m--; } } } }else if(prob < 90){ type = 1; rep(i,M) station_x0[i] = station_x[i], station_y0[i] = station_y[i]; int n = xorshift()%M; station_x[n] += xorshift()%200 * (xorshift()%2 == 0 ? -1 : 1); station_y[n] += xorshift()%200 * (xorshift()%2 == 0 ? -1 : 1); chmax(station_x[n],0); chmin(station_x[n],1000); chmax(station_y[n],0); chmin(station_y[n],1000); }else{ type = 2; order0 = order; if(xorshift()%2 == 0){ int n = xorshift()%(si(order)-2)+1; order.insert(order.begin()+n, xorshift()%M+N); }else{ int n = xorshift()%(si(order)-2)+1; rep(_,200) if(order[n] < N){ n = xorshift()%(si(order)-2)+1; } if(order[n] >= N) order.erase(order.begin()+n); } } ll score1 = cal_score(order); if(score0 < score1){ score = score1; }else{ if((double)(xorshift()%infi)/(double)infi < exp((score1-score0)/T)){ score = score1; }else{ if(type == 0 || type == 2) order = order0; else if(type == 1) { rep(i,M) station_x[i] = station_x0[i], station_y[i] = station_y0[i]; } } } timer.get_time(); T = T1 + (T0-T1)*timer.now()/TIME_LIMIT; if(LOCAL && loop%1000 == 0) cerr << loop csp score csp timer.now() csp T << endl; } cerr << score csp timer.get_time() << endl; print_ans(); } void print_ans(){ rep(i,M) cout << station_x[i] csp station_y[i] << endl; cout << si(order) << endl; rep(i,si(order)){ if(order[i] < N) cout << 1 csp order[i]+1 << endl; else cout << 2 csp order[i]-N+1 << endl; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); SimulatedAnnealing solver; solver.solve(); return 0; }