結果

問題 No.5007 Steiner Space Travel
ユーザー HaaHaa
提出日時 2022-07-30 16:20:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 952 ms / 1,000 ms
コード長 5,014 bytes
コンパイル時間 1,935 ms
実行使用メモリ 5,164 KB
スコア 8,163,110
最終ジャッジ日時 2022-07-30 16:21:04
合計ジャッジ時間 32,286 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 952 ms
4,900 KB
testcase_01 AC 909 ms
4,904 KB
testcase_02 AC 924 ms
5,164 KB
testcase_03 AC 930 ms
5,160 KB
testcase_04 AC 908 ms
5,160 KB
testcase_05 AC 933 ms
4,900 KB
testcase_06 AC 910 ms
4,904 KB
testcase_07 AC 933 ms
4,900 KB
testcase_08 AC 932 ms
5,156 KB
testcase_09 AC 910 ms
4,904 KB
testcase_10 AC 930 ms
5,160 KB
testcase_11 AC 906 ms
4,904 KB
testcase_12 AC 932 ms
4,900 KB
testcase_13 AC 928 ms
5,156 KB
testcase_14 AC 910 ms
4,904 KB
testcase_15 AC 935 ms
5,156 KB
testcase_16 AC 908 ms
4,904 KB
testcase_17 AC 936 ms
5,160 KB
testcase_18 AC 916 ms
4,904 KB
testcase_19 AC 918 ms
4,904 KB
testcase_20 AC 934 ms
4,900 KB
testcase_21 AC 910 ms
5,160 KB
testcase_22 AC 932 ms
4,900 KB
testcase_23 AC 907 ms
4,900 KB
testcase_24 AC 935 ms
4,900 KB
testcase_25 AC 931 ms
5,160 KB
testcase_26 AC 907 ms
4,900 KB
testcase_27 AC 934 ms
5,156 KB
testcase_28 AC 910 ms
4,900 KB
testcase_29 AC 928 ms
4,900 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘ll solve()’ 内:
main.cpp:163:22: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  163 |             for(auto [t,r]:ans[i]){
      |                      ^
main.cpp:140:17: 警告: ‘ry’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  140 |                 if(ry==0){
      |                 ^~

ソースコード

diff # 

#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;

const bool DEBUG=0;

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=1000;
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 input_debug(int fnum){
    string name="";
    if(fnum<1000) name+='0';
    if(fnum<100) name+='0';
    if(fnum<10) name+='0';
    name+=to_string(fnum);
    name+=".txt";
    ifstream ifs(("/mnt/c/CP/work/input/"+name).c_str(),ios::in);
    if(!ifs)
        cout << "error" << endl;
    cout << name << " ";
    ifs >> N >> M;
    REP(i,N) ifs >> P[i].x >> P[i].y;
}

ll 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, mincost=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()%4;
        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;
                if(sss[r1].size()==2)
                    continue;
                r2=rand()%sss[r1].size();
                auto it=sss[r1].begin();
                REP(i,r2) it++;
                r2=*it;
                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(j==k)
                    continue;
                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(mincost,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);
        }
    }
    if(!DEBUG){
        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;
            }
        }
    }
    return mincost;
}

int main(){
    if(!DEBUG){
        start=clock(); T=T0;
        input();
        solve();
    }
    else{
        int t=50;
        ll scoresum=0;
        REP(i,t){
            start=clock(); T=T0;
            input_debug(i);
            ll cost=solve();
            ll score=1e9/(1000+sqrt(cost));
            scoresum+=score;
            cout << score << endl;
        }
        cout << scoresum << endl;
    }
    return 0;
}
0