結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 961 ms
4,900 KB
testcase_01 AC 967 ms
4,904 KB
testcase_02 AC 955 ms
4,900 KB
testcase_03 AC 960 ms
4,900 KB
testcase_04 AC 967 ms
4,900 KB
testcase_05 AC 960 ms
4,904 KB
testcase_06 AC 964 ms
6,948 KB
testcase_07 AC 956 ms
4,900 KB
testcase_08 AC 954 ms
4,904 KB
testcase_09 AC 959 ms
4,900 KB
testcase_10 AC 958 ms
4,900 KB
testcase_11 AC 954 ms
4,904 KB
testcase_12 AC 955 ms
4,904 KB
testcase_13 AC 953 ms
4,904 KB
testcase_14 AC 981 ms
6,952 KB
testcase_15 AC 973 ms
4,904 KB
testcase_16 AC 967 ms
4,900 KB
testcase_17 AC 957 ms
6,952 KB
testcase_18 AC 955 ms
4,900 KB
testcase_19 AC 962 ms
6,948 KB
testcase_20 AC 964 ms
4,904 KB
testcase_21 AC 964 ms
4,900 KB
testcase_22 AC 959 ms
6,948 KB
testcase_23 AC 960 ms
6,948 KB
testcase_24 AC 966 ms
4,904 KB
testcase_25 AC 967 ms
6,952 KB
testcase_26 AC 960 ms
4,900 KB
testcase_27 AC 960 ms
4,904 KB
testcase_28 AC 961 ms
4,904 KB
testcase_29 AC 970 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],XX[N + 1];
ll flag = 0;
ll X[N + 1];
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);
void calc_dis(){
    for(ll i = 0;i < N;i++){
        for(ll j = 0;j < N;j++){
            if(i == j) Dis[i][j] = 0;
            else if(i > j) Dis[i][j] = Dis[j][i];
            else{
                ll ans = 25 * ((A[i] - A[j]) * (A[i] - A[j]) - (B[i] - B[j]) * (B[i] - B[j]));
                for(ll p = 0;p < M;p++){
                    for(ll q = 0;q < M;q++){
                        ll d1 = 5 * ((A[i] - C[p]) * (A[i] - C[p]) + (B[i] - D[p]) * (B[i] - D[p]));
                        ll d2 = 1 * ((C[q] - C[p]) * (C[q] - C[p]) + (D[q] - D[p]) * (D[q] - D[p]));
                        ll d3 = 5 * ((C[q] - A[j]) * (C[q] - A[j]) + (D[q] - B[j]) * (D[q] - B[j]));
                        ll d = d1 + d2 + d3;
                        ans = min(ans,d);
                    }
                }
                Dis[i][j] = ans;
            }
        }
    }
}
void calc_dis_last(){
    for(ll i = 0;i < N;i++){
        for(ll j = 0;j < N;j++){
            if(i == j) Dis[i][j] = 0;
            else if(i > j){
                Dis[i][j] = Dis[j][i];
                DA[i][j] = DB[j][i];
                DB[i][j] = DA[j][i];
            }
            else{
                ll ans = 25 * ((A[i] - A[j]) * (A[i] - A[j]) - (B[i] - B[j]) * (B[i] - B[j]));
                ll a = -1,b = -1;
                for(ll p = 0;p < M;p++){
                    for(ll q = 0;q < M;q++){
                        ll d1 = 5 * ((A[i] - C[p]) * (A[i] - C[p]) + (B[i] - D[p]) * (B[i] - D[p]));
                        ll d2 = 1 * ((C[q] - C[p]) * (C[q] - C[p]) + (D[q] - D[p]) * (D[q] - D[p]));
                        ll d3 = 5 * ((C[q] - A[j]) * (C[q] - A[j]) + (D[q] - B[j]) * (D[q] - B[j]));
                        ll d = d1 + d2 + d3;
                        if(ans > d){
                            ans = d;
                            a = p;
                            b = q;
                        }
                    }
                }
                Dis[i][j] = ans;
                DA[i][j] = a;
                DB[i][j] = b;
            }
        }
    }
}
system_clock::time_point start;
vector<ll> ans1,ans2;
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_dis();
    now_score = 0;
    for(ll i = 0;i < N;i++){
        now_score += Dis[X[i]][X[i + 1]];
    }
    used_time = 0;
    temp = starttemp + (endtemp - starttemp) * used_time / time_limit;
    while(1){
        for(ll i = 0;i < 100000;i++){
            ll x = mt() % (N - 1) + 1;
            ll y = mt() % (N - 1) + 1;
            if(x == y) continue;
            if(x > y) swap(x,y);
            ll new_score = now_score;
            new_score -= Dis[X[x - 1]][X[x]];
            new_score -= Dis[X[y]][X[y + 1]];
            new_score += Dis[X[x - 1]][X[y]];
            new_score += Dis[X[x]][X[y + 1]];
            double probability = exp((now_score - new_score) / temp);
            bool FORCE_NEXT = probability > (ld)(mt() % BIG) / BIG;
            if(FORCE_NEXT){
                now_score = new_score;
                swap(X[x],X[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;
        if(flag){
            double probability = exp((old_score - now_score) / temp);
            bool FORCE_NEXT = probability > (ld)(mt() % BIG) / BIG;
            if(!FORCE_NEXT){
                now_score = old_score;
                for(ll i = 0;i < M;i++){
                    C[i] = CC[i];
                    D[i] = DD[i];
                }
                for(ll i = 0;i <= N;i++) X[i] = XX[i];
                calc_dis();
            }
            flag = 0;
        }

        if(mt() % 2 == 0){
            //あとでC,Dの変更を書く
            flag = 1;
            for(ll i = 0;i < 2;i++){
                ll id = mt() % M;
                for(ll i = 0;i < M;i++){
                    CC[i] = C[i];
                    DD[i] = D[i];
                }
                for(ll i = 0;i <= N;i++){
                    XX[i] = X[i];
                }
                C[id] = mt() % 1000;
                D[id] = mt() % 1000;
            }
            calc_dis();
        }
    }
    calc_dis_last();
    for(ll i = 0;i < M;i++) cout << C[i] << " " << D[i] << endl;
    for(ll i = 0;i <= N;i++){
        ans1.emplace_back(1);
        ans2.emplace_back(X[i] + 1);
        if(i < N){
            ll a = DA[X[i]][X[i + 1]],b = DB[X[i]][X[i + 1]];
            if(a != -1){
                if(a == b){
                    ans1.emplace_back(2);
                    ans2.emplace_back(a + 1);
                }
                else{
                    ans1.emplace_back(2);
                    ans2.emplace_back(a + 1);
                    ans1.emplace_back(2);
                    ans2.emplace_back(b + 1);
                }
            } 
        }
    }
    cout << (ll)ans1.size() << endl;
    for(ll i = 0;i < (ll)ans1.size();i++) cout << ans1[i] << " " << ans2[i] << endl;
}
0