結果

問題 No.5007 Steiner Space Travel
ユーザー tanakatanaka
提出日時 2023-04-27 01:15:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 3,907 bytes
コンパイル時間 2,556 ms
コンパイル使用メモリ 206,032 KB
実行使用メモリ 4,372 KB
スコア 1,221,702
最終ジャッジ日時 2023-04-27 01:15:09
合計ジャッジ時間 4,761 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 2 ms
4,368 KB
testcase_04 AC 2 ms
4,372 KB
testcase_05 AC 2 ms
4,372 KB
testcase_06 AC 3 ms
4,368 KB
testcase_07 AC 2 ms
4,368 KB
testcase_08 AC 2 ms
4,372 KB
testcase_09 AC 2 ms
4,372 KB
testcase_10 AC 2 ms
4,372 KB
testcase_11 AC 2 ms
4,368 KB
testcase_12 AC 2 ms
4,368 KB
testcase_13 AC 2 ms
4,368 KB
testcase_14 AC 2 ms
4,372 KB
testcase_15 AC 3 ms
4,372 KB
testcase_16 AC 2 ms
4,368 KB
testcase_17 AC 2 ms
4,372 KB
testcase_18 AC 2 ms
4,372 KB
testcase_19 AC 2 ms
4,372 KB
testcase_20 AC 2 ms
4,372 KB
testcase_21 AC 2 ms
4,368 KB
testcase_22 AC 2 ms
4,372 KB
testcase_23 AC 2 ms
4,368 KB
testcase_24 AC 2 ms
4,368 KB
testcase_25 AC 2 ms
4,368 KB
testcase_26 AC 2 ms
4,368 KB
testcase_27 AC 2 ms
4,368 KB
testcase_28 AC 2 ms
4,368 KB
testcase_29 AC 2 ms
4,372 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:118:47: 警告: narrowing conversion of ‘(mt.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()() % 1001)’ from ‘std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
  118 |     rep(i, M_SIZE) base.wp.push_back({2, {mt()%1001, mt()%1001}});
      |                                           ~~~~^~~~~
main.cpp:118:58: 警告: narrowing conversion of ‘(mt.std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::operator()() % 1001)’ from ‘std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
  118 |     rep(i, M_SIZE) base.wp.push_back({2, {mt()%1001, mt()%1001}});
      |                                                      ~~~~^~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep3(i, n, m) for (int i = m; i < (int)(n); i++)
#define repr(i, n) for (int i = n-1; i >= 0; i--)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define ll long long

#define N_SIZE 100
#define M_SIZE 8
#define ALPHA 5

using namespace std;

//定数周り
int imax=2147483647;
ll lmax=9223372036854775807;

//焼きなましの定数
double TIME_LIMIT=985;
double start_temp=400000.0;
double end_temp=1000.0;

//乱数の準備
// int seed=1;
auto seed=(unsigned)time(NULL);
mt19937_64 mt(seed);

struct Pos{
	int x;
    int y;

    Pos(){}
    Pos(int ix, int iy){
        x=ix;
        y=iy;
    }

	bool operator<(const Pos &in) const{
		return x!=in.x ? x<in.x : y<in.y;
	};

    int euclid(Pos p){
        return (p.x-x)*(p.x-x)+(p.y-y)*(p.y-y);
    }
};

struct WayPoint{
    int t;
    Pos pos;

    WayPoint(){}
    WayPoint(int it, Pos ipos){
        t=it;
        pos=ipos;
    }

    int dist(WayPoint wp){
        int dis=pos.euclid(wp.pos);
        if(t==1) dis*=ALPHA;
        if(wp.t==1) dis*=ALPHA;
        return dis;
    }
};

struct Travel{
    Pos stations[M_SIZE];
    vector<WayPoint> wp;
    vector<int> tour;

    int score(){
        ll s=0;
        rep(i, wp.size()-1){
            s+=wp[i].dist(wp[i+1]);
        }
        double base=1000000000.0;
        base/=1000+sqrt(s);
        base=round(base);
        return base;
    }

    void print(){
        rep3(i, N_SIZE+M_SIZE, N_SIZE) cout<< wp[i].pos.x SP << wp[i].pos.y <<endl;
        cout<< tour.size() <<endl;
        rep(i, tour.size()){
            cout<< wp[tour[i]].t SP;
            if(wp[tour[i]].t==1) cout<< tour[i]+1 <<endl;
            else cout<< tour[i]-N_SIZE+1 <<endl;
        }
    }
};

//入力など
int n, m;
Pos planets[N_SIZE];

void inpt(){
    cin>> n >> m;
    rep(i, N_SIZE){
        cin>> planets[i].x >> planets[i].y;
        // a[i]=mt()%1001;
        // b[i]=mt()%1001;
        // cout<< a[i] SP << b[i] <<endl;
    }
}

int main(){
    //開始時間の計測
    std::chrono::system_clock::time_point start, current;
    start = chrono::system_clock::now();

    //入力
    inpt();

    Travel base;
    rep(i, N_SIZE) base.wp.push_back({1, planets[i]});
    rep(i, M_SIZE) base.wp.push_back({2, {mt()%1001, mt()%1001}});

    rep(i, N_SIZE) base.tour.push_back(i);
    base.tour.push_back(0);
    base.print();
    return 0;

    //焼きなまし
    int lp=0;
    while (true) { // 時間の許す限り回す
        lp++;
        //cout<< lp <<endl;
        if(lp%1000==0){
            current = chrono::system_clock::now(); // 現在時刻
            if (chrono::duration_cast<chrono::milliseconds>(current - start).count() > TIME_LIMIT) break;
        }
        
        //if(lp==20000) break;

        int type=mt()%4+1;
        //cout<< "type:" << type <<endl;
        if(type==1){
            // 惑星訪問の順番入れ替え
        }else if(type==2){
            // ステーション移動
        }else if(type==3){
            // ステーション挿入
        }else{
            // ステーション削除
        }

        int b_sco, n_sco;
        // 温度関数
        double temp = start_temp + (end_temp - start_temp) * chrono::duration_cast<chrono::milliseconds>(current - start).count() / TIME_LIMIT;
        // 遷移確率関数(最大化の場合)
        double prob = exp((n_sco-b_sco)/temp);

        if (prob > (mt()%imax)/(double)imax) { // 確率probで遷移する
        //if (nsco<psco) {
            b_sco=n_sco;
            // cout<< "lp:" << lp <<endl;
            //cout<< n_sco <<endl;
        }else{
            if(type==1){
            }else if(type==2){
            }else if(type==3){
            }else{
            }
        }
    }

    // cout<< chrono::duration_cast<chrono::milliseconds>(current - start).count() <<endl;

	return 0;
}
0