結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー kaede2020
提出日時 2022-07-30 15:57:35
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 64 ms / 1,000 ms
コード長 2,481 bytes
コンパイル時間 1,209 ms
実行使用メモリ 5,164 KB
スコア 6,122,904
最終ジャッジ日時 2022-07-30 15:57:40
合計ジャッジ時間 4,924 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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.n>//INT_MAX
//#include <math.n>//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];
bool visited[300];
int P[300];
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 sqrt((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 += 5*5*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;    
}
void terry_yukico::simulate(){
    double best_score=evaluateScore();
    rep(i,200000){
        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;
        if(best_score>=now_score)best_score=now_score;
        else reverse(P+l,P+r+1);
    }
}
void terry_yukico::output(){
    rep(i,m){
        cout<<i+1<<" "<<i+1<<endl;
    }
    cout<<n+1<<endl;
    for(int i=1;i<=n+1;i++)cout<<1<<" "<<P[i]<<endl;
}
int main(){
    terry_yukico state;
    state.input();
    state.init();
    state.simulate();
    state.output();
    return 0;
}
0