結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 15:52:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 905 ms / 1,000 ms |
コード長 | 6,723 bytes |
コンパイル時間 | 1,901 ms |
実行使用メモリ | 6,952 KB |
スコア | 5,828,614 |
最終ジャッジ日時 | 2022-07-30 15:52:39 |
合計ジャッジ時間 | 31,967 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder>using namespace std;//using namespace atcoder;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define repab(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)#define repabc(i, a, b, c) for (int i = (int)(a); i <= (int)(b); i += c)#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)#define rrepab(i, a, b) for (int i = (int)(b); i >= (int)(a); i--)#define rrepabc(i, a, b, c) for (int i = (int)(b); i >= (int)(a); i-=c)#define printl(...) cerr << "LINE=" << __LINE__ << " "; print(__VA_ARGS__)void in_print() {}template <class Head, class... Tail>void in_print(Head&& head, Tail&&... tail){cerr << "," << head;in_print(forward<Tail>(tail)...);}void print() {}template <class Head, class... Tail>void print(Head&& head, Tail&&... tail){cerr << head;in_print(forward<Tail>(tail)...);cerr << endl;}unsigned int randxor(){static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;unsigned int t;t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );}//char grid[8][8];//static const int dx[] = {0,-1,0,1,1,-1,-1,1};//static const int dy[] = {-1,0,1,0,1,1,-1,-1};//static const char dir[] = {'L','U','R','D'};auto start_time = chrono::system_clock::now();auto end_time = chrono::system_clock::now();//if (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() > 500)int N = 100;int M = 8;int planet[100][2];int station[8][2];int alpha = 5;typedef vector<int> vi;typedef vector<vector<int>> vvi;void load_data(){cin >> N >> M;rep(i, N) rep(j, 2) cin >> planet[i][j];rep(i, 8) rep(j, 2) station[i][j] = i*100;}double calc_score(vvi st, vvi &ans){long long energy = 0;int x = planet[0][0];int y = planet[0][1];int nowt = 1;rep(i, (int)ans.size()) {if (ans[i][0] == 1) {if (nowt == 1) energy += 25 * ((x-planet[ans[i][1]][0])*(x-planet[ans[i][1]][0]) + (y-planet[ans[i][1]][1])*(y-planet[ans[i][1]][1]));else energy += 5 * ((x-planet[ans[i][1]][0])*(x-planet[ans[i][1]][0]) + (y-planet[ans[i][1]][1])*(y-planet[ans[i][1]][1]));x = planet[ans[i][1]][0];y = planet[ans[i][1]][1];}else {if (nowt == 2) energy += ((x-st[ans[i][1]][0])*(x-st[ans[i][1]][0]) + (y-st[ans[i][1]][1])*(y-st[ans[i][1]][1]));else energy += 5 * ((x-st[ans[i][1]][0])*(x-st[ans[i][1]][0]) + (y-st[ans[i][1]][1])*(y-st[ans[i][1]][1]));x = st[ans[i][1]][0];y = st[ans[i][1]][1];}nowt = ans[i][0];}return round(1000000000.0/(1000.0 + sqrt(energy)));}void make_first_ans(vvi &fans){vi dd = {1, 0};fans.push_back(dd);repab(i, 1, N-1) {vi dd = {1, i};fans.push_back(dd);}vi dc = {1, 0};fans.push_back(dc);}void print_ans(vvi &st, vvi &ans){rep(i, 8) cout << st[i][0] << " " << st[i][1] << endl;cout << ans.size() << endl;rep(i, (int)ans.size()) cout << ans[i][0] << " " << ans[i][1]+1 << endl;}struct STATE {double score;vvi robo;vvi move;vi cnt;};void simulated_annealing(){double start_tmp = 15;double end_tmp = 1;int sa_end_time = 900;double fsc = 0.0;vvi frobo;rep(i, 8) frobo.push_back({station[i][0], station[i][1]});vvi fmove;make_first_ans(fmove);vi fcnt;rep(i, N) {if (i == 0) fcnt.push_back(2);else fcnt.push_back(1);}STATE state = {fsc, frobo, fmove, fcnt};int cnt = 0;while (true) {if (cnt % 100 == 0) {end_time = chrono::system_clock::now();if (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() > sa_end_time) break;}cnt += 1;STATE nxt = state;int opt = randxor() % 4;//int opt = 3;if (opt == 0) {int posi = randxor() % 8;nxt.robo[posi][0] += -min(50, nxt.robo[posi][0]) + (randxor() % max(1, min(50, nxt.robo[posi][0])+min(50, 1000-nxt.robo[posi][0])));nxt.robo[posi][1] += -min(50, nxt.robo[posi][1]) + (randxor() % max(1, min(50, nxt.robo[posi][1])+min(50, 1000-nxt.robo[posi][1])));double nextscore = calc_score(nxt.robo, nxt.move);nxt.score = nextscore;double nowscore = state.score;double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;double prob = exp((nextscore - nowscore)/temp);if (prob > (randxor() % 10000)/10000.0) {state = nxt;}}else if (opt == 1) {int posi = 1 + randxor() % (max(1, (int)nxt.move.size()-2));int tp = randxor() % 10;if (tp < 3) {int ad = randxor() % 8;nxt.move.insert(nxt.move.begin() + posi, {2, ad});}else {int ad = randxor() % 100;nxt.move.insert(nxt.move.begin() + posi, {1, ad});nxt.cnt[ad] += 1;}double nextscore = calc_score(nxt.robo, nxt.move);nxt.score = nextscore;double nowscore = state.score;double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;double prob = exp((nextscore - nowscore)/temp);if (prob > (randxor() % 10000)/10000.0) {state = nxt;}}else if ( opt == 2) {int posi = 1 + (randxor() % (max(1, (int)nxt.move.size() - 2)));if (nxt.move[posi][0] == 1) {if (nxt.cnt[nxt.move[posi][1]] > 1) {nxt.cnt[nxt.move[posi][1]] -= 1;nxt.move.erase(nxt.move.begin() + posi);}}else nxt.move.erase(nxt.move.begin() + posi);double nextscore = calc_score(nxt.robo, nxt.move);nxt.score = nextscore;double nowscore = state.score;double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;double prob = exp((nextscore - nowscore)/temp);if (prob > (randxor() % 10000)/10000.0) {state = nxt;}}else {int posi = 1 + (randxor() % max(1, (int)nxt.move.size() - 3));swap(nxt.move[posi], nxt.move[posi+1]);double nextscore = calc_score(nxt.robo, nxt.move);nxt.score = nextscore;double nowscore = state.score;double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;double prob = exp((nextscore - nowscore)/temp);if (prob > (randxor() % 10000)/10000.0) {state = nxt;}}}print("cnt=", cnt);print(state.score);print_ans(state.robo, state.move);}int main(){load_data();simulated_annealing();}