結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー Haa
提出日時 2022-07-30 15:25:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 965 ms / 1,000 ms
コード長 4,087 bytes
コンパイル時間 2,184 ms
実行使用メモリ 6,952 KB
スコア 7,881,253
最終ジャッジ日時 2022-07-30 15:25:40
合計ジャッジ時間 32,900 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘void solve()’ 内:
main.cpp:141:18: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  141 |         for(auto [t,r]:ans[i]){
      |                  ^
main.cpp:119:17: 警告: ‘ry’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  119 |                 if(ry==0){
      |                 ^~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
template<typename T> bool chmax(T &x, const T &y) {return (x<y)?(x=y,true):false;};
template<typename T> bool chmin(T &x, const T &y) {return (x>y)?(x=y,true):false;};
constexpr ll MOD=998244353;
constexpr ll INF=2e18;

struct Point{
    int x, y;
};

inline int pdist(const Point& p1, const Point& p2){
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

const double TL=0.9;
const double T0=8000;
const double T1=10;
double start, T;

int alp=5;
int N, M;
vector<Point> P(100);

Point cog(const set<int>& s){
    int sz=s.size();
    int xsum=0, ysum=0;
    for(auto i:s){
        xsum+=P[i].x;
        ysum+=P[i].y;
    }
    return {xsum/sz,ysum/sz};
}

void input(){
    cin >> N >> M;
    REP(i,N) cin >> P[i].x >> P[i].y;
}

void solve(){
    vector<vector<int>> dist(N,vector<int>(N));
    REP(i,N)REP(j,N) dist[i][j]=pdist(P[i],P[j]);
    vector<int> ord(N);
    iota(ALL(ord),0);
    vector<set<int>> sss(M);
    REP(i,M) sss[i]={ord[i],ord[(i+1)%N]};
    vector<Point> ssp(M);
    REP(i,M) ssp[i]=cog(sss[i]);
    ll cost=0, maxcost=INF;
    REP(i,N) cost+=alp*alp*dist[ord[i]][ord[(i+1)%N]];
    vector<Point> ansssp;
    vector<vector<pair<int,int>>> ans;
    int rcnt=0;
    for(rcnt=0;true;rcnt++){
        int rx, ry, r1, r2;
        rx=rand()%2;
        if(rx!=0){
            r1=rand()%N+1;
            r2=rand()%N+1;
            if(r1>r2) swap(r1,r2);
            reverse(ord.begin()+r1,ord.begin()+r2);
        }
        else{
            ry=rand()%2;
            if(ry==0){
                r1=rand()%M;
                r2=rand()%N;
                if(sss[r1].find(r2)!=sss[r1].end())
                    continue;
                sss[r1].insert(r2);
                ssp[r1]=cog(sss[r1]);
            }
            else{
                r1=rand()%M;
                r2=rand()%N;
                if(sss[r1].size()==2)
                    continue;
                if(sss[r1].find(r2)==sss[r1].end())
                    continue;
                sss[r1].erase(r2);
                ssp[r1]=cog(sss[r1]);
            }
        }
        vector<vector<pair<int,int>>> pans(N);
        ll newcost=0;
        REP(i,N){
            ll mcost=alp*alp*pdist(P[ord[i]],P[ord[(i+1)%N]]);
            pans[i]={{0,ord[i]}};
            REP(j,M)REP(k,M+1){
                if(k==M){
                    if(chmin(mcost,(ll)alp*(pdist(P[ord[i]],ssp[j])+pdist(ssp[j],P[ord[(i+1)%N]])))){
                        pans[i]={{0,ord[i]},{1,j}};
                    }
                }
                else{
                    if(chmin(mcost,(ll)alp*(pdist(P[ord[i]],ssp[j])+pdist(ssp[k],P[ord[(i+1)%N]]))+pdist(ssp[j],ssp[k]))){
                        pans[i]={{0,ord[i]},{1,j},{1,k}};
                    }
                }
            }
            newcost+=mcost;
            if(i==N-1)
                pans[i].push_back({0,0});
        }
        if(chmin(maxcost,newcost)){
            ans=pans;
            ansssp=ssp;
        }
        if(rand()%1000000>exp((newcost-cost)/T)*1e6)
            cost=newcost;
        else{
            if(rx!=0){
                reverse(ord.begin()+r1,ord.begin()+r2);
            }
            else{
                if(ry==0){
                    sss[r1].erase(r2);
                    ssp[r1]=cog(sss[r1]);
                }
                else{
                    sss[r1].insert(r2);
                    ssp[r1]=cog(sss[r1]);
                }
            }
        }  
        if(rcnt%50==0){
            double t=(double)(clock()-start)/CLOCKS_PER_SEC/TL;
            if(t>=1.0)
                break;
            T=pow(T0,(t-0.6)/0.4)*pow(T1,t-0.6);
        }
    }
    REP(i,M) cout << ansssp[i].x << " " << ansssp[i].y << endl;
    int szs=0;
    REP(i,N) szs+=ans[i].size();
    cout << szs << endl;
    REP(i,N){
        for(auto [t,r]:ans[i]){
            cout << t+1 << " " << r+1 << endl;
        }
    }
}

int main(){
    start=clock();
    input();
    solve();
    return 0;
}
0