結果

問題 No.5007 Steiner Space Travel
ユーザー human
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0