結果

問題 No.5007 Steiner Space Travel
ユーザー hiikunZhiikunZ
提出日時 2022-07-30 17:53:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 964 ms / 1,000 ms
コード長 10,749 bytes
コンパイル時間 2,785 ms
実行使用メモリ 5,164 KB
スコア 7,230,363
最終ジャッジ日時 2022-07-30 17:54:00
合計ジャッジ時間 34,242 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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],CC[M],DD[M],Y2[M],Y[M],CNT[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.96;
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 ty = mt() % 20000;
            if(ty < 1000){
                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);
                }
            }
            else if(ty < 17000){
                ll id = mt() % M;
                ll x = C[id] + 100 - (mt() % 200);
                ll y = D[id] + 100 - (mt() % 200);
                if(x < 0 || x > 1000 || y < 0 || y > 1000) continue;
                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);
                }
            }
            else{
                {
                    for(ll i = 0;i < M;i++){
                        Y[i] = 0;
                        Y2[i] = 0;
                        CNT[i] = 0;
                    }
                    for(ll i = 0;i < N;i++){
                        ll x = X[i];
                        Y[x] += A[i];
                        Y2[x] += A[i] * A[i];
                        CNT[x]++;
                    }
                    for(ll i = 0;i < M;i++){
                        if(CNT[i] != 0) CC[i] = round((1.0 * (Y[i]) / (CNT[i])));
                    }
                }
                {
                    for(ll i = 0;i < M;i++){
                        Y[i] = 0;
                        Y2[i] = 0;
                        CNT[i] = 0;
                    }
                    for(ll i = 0;i < N;i++){
                        ll x = X[i];
                        Y[x] += B[i];
                        Y2[x] += B[i] * B[i];
                        CNT[x]++;
                    }
                    for(ll i = 0;i < M;i++){
                        if(CNT[i] != 0) DD[i] = round((1.0 * (Y[i]) / (CNT[i])));
                    }
                }
                for(ll i = 0;i < M;i++){
                    swap(C[i],CC[i]);
                    swap(D[i],DD[i]);
                }
                ll new_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;
                        }
                    }
                    new_score += dis;
                    PP[i] = dis;
                    XX[i] = a;
                }
                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 < N;i++){
                        X[i] = XX[i];
                        P[i] = PP[i];
                    }
                }
                else{
                    for(ll i = 0;i < M;i++){
                        swap(C[i],CC[i]);
                        swap(D[i],DD[i]);
                    }
                }
            }
        }
        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++){
            Y[i] = 0;
            Y2[i] = 0;
            CNT[i] = 0;
        }
        for(ll i = 0;i < N;i++){
            ll x = X[i];
            Y[x] += A[i];
            Y2[x] += A[i] * A[i];
            CNT[x]++;
        }
        for(ll i = 0;i < M;i++){
            if(CNT[i] != 0) CC[i] = round((1.0 * (Y[i]) / (CNT[i])));
        }
    }
    {
        for(ll i = 0;i < M;i++){
            Y[i] = 0;
            Y2[i] = 0;
            CNT[i] = 0;
        }
        for(ll i = 0;i < N;i++){
            ll x = X[i];
            Y[x] += B[i];
            Y2[x] += B[i] * B[i];
            CNT[x]++;
        }
        for(ll i = 0;i < M;i++){
            if(CNT[i] != 0) DD[i] = round((1.0 * (Y[i]) / (CNT[i])));
        }
    }
    
    for(ll i = 0;i < M;i++) cout << C[i] << " " << D[i] << endl;
    vector<ll> B,PER(M);
    ll tp = 998244353;
    for(ll i = 0;i < M;i++){
        PER[i] = i;
    }
    do{
        ll s = 0;
        for(ll i = 0;i < M;i++){
            ll I = PER[i];
            ll J = PER[(i + 1) % M];
            s += (C[I] - C[J]) * (C[I] - C[J]) + (D[I] - D[J]) * (D[I] - D[J]);
        }
        if(tp > s){
            tp = s;
            B = PER;
        }
    }
    while(next_permutation(PER.begin(),PER.end()));
    for(ll I = 0;I < M;I++){
        ll i = B[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