結果

問題 No.5007 Steiner Space Travel
ユーザー kaede2020kaede2020
提出日時 2022-07-30 17:45:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 66 ms / 1,000 ms
コード長 4,555 bytes
コンパイル時間 1,345 ms
実行使用メモリ 5,164 KB
スコア 6,804,818
最終ジャッジ日時 2022-07-30 17:45:27
合計ジャッジ時間 4,754 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
3,864 KB
testcase_01 AC 53 ms
4,904 KB
testcase_02 AC 57 ms
4,904 KB
testcase_03 AC 58 ms
5,160 KB
testcase_04 AC 53 ms
4,900 KB
testcase_05 AC 53 ms
4,904 KB
testcase_06 AC 54 ms
4,904 KB
testcase_07 AC 53 ms
5,160 KB
testcase_08 AC 53 ms
5,160 KB
testcase_09 AC 54 ms
5,156 KB
testcase_10 AC 58 ms
5,164 KB
testcase_11 AC 66 ms
4,900 KB
testcase_12 AC 61 ms
4,904 KB
testcase_13 AC 53 ms
4,900 KB
testcase_14 AC 52 ms
4,900 KB
testcase_15 AC 53 ms
4,900 KB
testcase_16 AC 57 ms
5,160 KB
testcase_17 AC 57 ms
4,908 KB
testcase_18 AC 58 ms
4,904 KB
testcase_19 AC 53 ms
4,900 KB
testcase_20 AC 53 ms
4,904 KB
testcase_21 AC 53 ms
4,904 KB
testcase_22 AC 53 ms
5,160 KB
testcase_23 AC 54 ms
5,164 KB
testcase_24 AC 52 ms
4,904 KB
testcase_25 AC 52 ms
5,160 KB
testcase_26 AC 52 ms
4,900 KB
testcase_27 AC 52 ms
4,904 KB
testcase_28 AC 51 ms
5,156 KB
testcase_29 AC 52 ms
3,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//fixed,setprecision
#include <limits.h>//INT_MAX
#include <math.h>//M_PI
#include <random>
#include <regex> // 正規表現
#include <time.h>
//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
std::random_device rnd;
std::mt19937 mt(rnd());
const int n=100;
const int m=8;
int x[300],y[300];
int eki_x[300];
int eki_y[300];
bool visited[300];
int P[300];
int Q[300];
int cnt=0;
int T[300];
vector<pair<int,int>>ans;
double Randouble() {return 1.0 * rand() / RAND_MAX;}
class terry_yukico{
    public:
    int ransu(int a,int b);
    double kyori(int p,int q);
    double evaluateScore();
    void input();
    void init();
    void simulate();
    void output();
};
int terry_yukico::ransu(int a, int b) {
    return a + rand() % (b - a + 1);
}
double terry_yukico::kyori(int p,int q){
    return 5*5*((x[p]-x[q])*(x[p]-x[q]) + (y[p]-y[q])*(y[p]-y[q]));
}
double terry_yukico::evaluateScore(){
    double sum = 0;
    for(int i=1;i<=n;i++) sum += kyori(P[i], P[i + 1]);
    return sum;
}
void terry_yukico::input(){
    int ni,mi;
    cin>>ni>>mi;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
}
void terry_yukico::init(){
    P[1] = 1; P[n+1 ] = 1;
    for (int i = 2; i <=n; i++) P[i] = i; 
    eki_x[0]=250;eki_y[0]=250; 
    eki_x[1]=250;eki_y[1]=500; 
    eki_x[2]=250;eki_y[2]=750; 
    eki_x[3]=500;eki_y[3]=250; 
    eki_x[4]=500;eki_y[4]=750; 
    eki_x[5]=750;eki_y[5]=250; 
    eki_x[6]=750;eki_y[6]=500;
    eki_x[7]=750;eki_y[7]=750;    
    cnt=0;
    rep(i,300)T[i]=1;
}
void terry_yukico::simulate(){
    double best_score=evaluateScore();
    for(int i=1;i<=200000;i++){
        int l=ransu(2,n);
        int r=ransu(2,n);
        if(l>r)swap(l,r);
        reverse(P+l,P+r+1);
        double now_score=evaluateScore();
        //cout<<"best:"<<best_score<<" tmp:"<<now_score<<endl;
        double T = 30.00 - 28.00 * (double)i / 200000.0;
        double Probability = exp(min(0.0, (best_score - now_score) / T));
        if (Randouble() < Probability) best_score=now_score;
        //if(best_score>=now_score)best_score=now_score;
        else reverse(P+l,P+r+1);
    }
    //cerr<<__LINE__<<"-----"<<endl;
    for(int i=1;i<=n+1;i++)Q[i]=P[i];
    rep(i,m){
        int sumx=0;
        int sumy=0;
        rep(j,12){
            sumx+=x[Q[j+12*i]];
            sumy+=y[Q[j+12*i]];
        }
        eki_x[i]=sumx/12;
        eki_y[i]=sumy/12;
    }
    cnt=0;
    //ans.emplace_back(1,1);
    for(int i=1;i<=n;i++){
        ans.emplace_back(1,Q[i]);
        if(T[i]==2)continue;
        if(T[i+1]==2)continue;
        int moto=5*5*((x[Q[i]]-x[Q[i+1]])*(x[Q[i]]-x[Q[i+1]]) + (y[Q[i]]-y[Q[i+1]])*(y[Q[i]]-y[Q[i+1]]));
        int after=moto;
        int num=-1;
        rep(j,m){
            int iki=5*((x[Q[i]]-eki_x[j])*(x[Q[i]]-eki_x[j]) + (y[Q[i]]-eki_y[j])*(y[Q[i]]-eki_y[j]));
            int kaeri=5*((x[Q[i+1]]-eki_x[j])*(x[Q[i+1]]-eki_x[j]) + (y[Q[i+1]]-eki_y[j])*(y[Q[i+1]]-eki_y[j]));
            if(after>iki+kaeri){
                after=iki+kaeri;
                num=j;
            }
        }
        if(moto>after){
            if(cnt>=300)break;
            //cerr<<"cnt"<<cnt<<"-----"<<endl;
            for(int j=cnt+n+1;j>=cnt+i+2;j--)P[j]=P[j-1];
            P[cnt+i+1]=num;
            T[cnt+i+1]=2;
            cnt++;
            ans.emplace_back(2,num+1);
        }
        //ans.push_back(1,Q[i+1]);
    }
    //ans.emplace_back(1,Q[n+1]);
    ans.emplace_back(1,1);
    //cerr<<__LINE__<<"-----"<<endl;
    
}
void terry_yukico::output(){
    rep(i,m)cout<<eki_x[i]<<" "<<eki_y[i]<<endl;
    cout<<ans.size()<<endl;
    //cout<<"1 1"<<endl;
    for(int i=0;i<ans.size();i++)cout<<ans[i].first<<" "<<ans[i].second<<endl;
    //cout<<"1 1"<<endl;
}
int main(){
    terry_yukico state;
    state.input();
    state.init();
    state.simulate();
    state.output();
    return 0;
}
0