結果

問題 No.5007 Steiner Space Travel
ユーザー hiikunZhiikunZ
提出日時 2022-07-30 17:02:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 4,622 bytes
コンパイル時間 2,970 ms
実行使用メモリ 6,948 KB
スコア 6,948,425
最終ジャッジ日時 2022-07-30 17:03:28
合計ジャッジ時間 33,382 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using namespace std::chrono;
using std::chrono::system_clock;
using std::chrono::seconds;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 0;//2024948111;
ld dotorad(ld K){return PI * K / 180.0;}
ld radtodo(ld K){return K * 180.0 / PI;}
mt19937 mt;
void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}
const ll N = 100,M = 8;
ll A[N],B[N],C[M],D[M];
ll CC[M],DD[M];
ll flag = 0;
ll X[N],P[N],XX[N],PP[N],IDID[N];
ll UPD;
ll Dis[N][N],DA[N][N],DB[N][N];
ll gomi;
ll now_score;
ll old_score;
ld used_time;
const ld starttemp = 100;
const ld endtemp = 1;
ld temp;
const ld time_limit = 0.95;
const ll BIG = (1LL << 30);

system_clock::time_point start;
vector<ll> ans1,ans2;
void calc_ans(){
    now_score = 0;
    for(ll i = 0;i < N;i++){
        ll dis = MAX,a = -1;
        for(ll j = 0;j < M;j++){
            ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
            if(d < dis){
                dis = d;
                a = j;
            }
        }
        now_score += dis;
        X[i] = a;
        P[i] = dis;
    }
}
int main(){
    start = system_clock::now();
    cin >> gomi >> gomi;
    for(ll i = 0;i < N;i++) cin >> A[i] >> B[i];
    for(ll i = 0;i < N;i++) X[i] = i;
    X[N] = 0;
    C[0] = 160;D[0] = 160;
    C[1] = 160;D[1] = 500;
    C[2] = 160;D[2] = 890;
    C[3] = 500;D[3] = 330;
    C[4] = 500;D[4] = 670;
    C[5] = 890;D[5] = 160;
    C[6] = 890;D[6] = 500;
    C[7] = 890;D[7] = 890;
    calc_ans();
    used_time = 0;
    temp = starttemp + (endtemp - starttemp) * used_time / time_limit;
    for(ll i = 0;i < N;i++){
        XX[i] = X[i];
        PP[i] = P[i];
    }
    while(1){
        for(ll w = 0;w < 1000;w++){
            ll id = mt() % M;
            ll x = mt() % 1001;
            ll y = mt() % 1001;
            ll new_score = 0;
            swap(C[id],x);
            swap(D[id],y);
            UPD = 0;
            for(ll i = 0;i < N;i++){
                if(X[i] == id){
                    ll dis = MAX,a = -1;
                    for(ll j = 0;j < M;j++){
                        ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
                        if(d < dis){
                            dis = d;
                            a = j;
                        }
                    }
                    new_score += dis;
                    PP[UPD] = dis;
                    XX[UPD] = a;
                    IDID[UPD] = i;
                    UPD++;
                }
                else{
                    const ll j = id;
                    ll d = (A[i] - C[j]) * (A[i] - C[j]) + (B[i] - D[j]) * (B[i] - D[j]);
                    if(P[i] > d){
                        PP[UPD] = d;
                        XX[UPD] = id;
                        IDID[UPD] = i;
                        UPD++;
                        new_score += d;
                    }
                    else new_score += P[i];
                }
                
            }
            double probability = exp((now_score - new_score) / temp);
            bool FORCE_NEXT = probability > (ld)(mt() % BIG) / BIG;
            if(FORCE_NEXT){
                now_score = new_score;
                for(ll i = 0;i < UPD;i++){
                    X[IDID[i]] = XX[i];
                    P[IDID[i]] = PP[i];
                }
            }
            else{
                swap(C[id],x);
                swap(D[id],y);
            }
        }
        used_time = duration_cast<microseconds>(system_clock::now() - start).count() * 1e-6;
        if(used_time > time_limit) break;
        temp = starttemp + (endtemp - starttemp) * used_time / time_limit;
    }
    calc_ans();
    for(ll i = 0;i < M;i++) cout << C[i] << " " << D[i] << endl;
    
    for(ll i = 0;i < M;i++){
        ans1.emplace_back(2);
        ans2.emplace_back(i + 1);
        for(ll j = 0;j < N;j++){    
            if(X[j] == i){
                ans1.emplace_back(1);
                ans2.emplace_back(j + 1);
                ans1.emplace_back(2);
                ans2.emplace_back(i + 1);
            }
        }
    }
    ll V = (ll)ans1.size(),I = -1;
    for(ll i = 0;i < V;i++){
        ans1.emplace_back(ans1[i]);
        ans2.emplace_back(ans2[i]);
        if(ans1[i] == 1 && ans2[i] == 1) I = i;
    }
    cout << V + 1 << endl;
    for(ll i = I;i < I + V;i++) cout << ans1[i] << " " << ans2[i] << endl;
    cout << "1 1" << endl;
}
0