結果

問題 No.5007 Steiner Space Travel
ユーザー HaaHaa
提出日時 2022-07-30 15:55:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 939 ms / 1,000 ms
コード長 4,902 bytes
コンパイル時間 2,353 ms
実行使用メモリ 4,188 KB
スコア 7,989,144
最終ジャッジ日時 2022-07-30 15:56:22
合計ジャッジ時間 32,728 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 909 ms
3,956 KB
testcase_01 AC 939 ms
3,860 KB
testcase_02 AC 913 ms
3,964 KB
testcase_03 AC 937 ms
3,988 KB
testcase_04 AC 909 ms
3,940 KB
testcase_05 AC 910 ms
3,980 KB
testcase_06 AC 926 ms
3,976 KB
testcase_07 AC 905 ms
3,940 KB
testcase_08 AC 936 ms
4,024 KB
testcase_09 AC 911 ms
3,856 KB
testcase_10 AC 911 ms
3,996 KB
testcase_11 AC 920 ms
4,004 KB
testcase_12 AC 910 ms
4,008 KB
testcase_13 AC 936 ms
3,860 KB
testcase_14 AC 909 ms
4,008 KB
testcase_15 AC 907 ms
3,944 KB
testcase_16 AC 910 ms
3,952 KB
testcase_17 AC 932 ms
3,868 KB
testcase_18 AC 933 ms
3,856 KB
testcase_19 AC 910 ms
4,004 KB
testcase_20 AC 911 ms
4,004 KB
testcase_21 AC 909 ms
3,868 KB
testcase_22 AC 910 ms
4,056 KB
testcase_23 AC 935 ms
3,956 KB
testcase_24 AC 908 ms
3,984 KB
testcase_25 AC 916 ms
4,032 KB
testcase_26 AC 908 ms
4,060 KB
testcase_27 AC 916 ms
4,188 KB
testcase_28 AC 935 ms
3,940 KB
testcase_29 AC 907 ms
3,980 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘ll solve()’ 内:
main.cpp:159:22: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  159 |             for(auto [t,r]:ans[i]){
      |                      ^
main.cpp:136:17: 警告: ‘ry’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  136 |                 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=800;
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;
                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(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();
        input();
        solve();
    }
    else{
        int t=50;
        ll scoresum=0;
        REP(i,t){
            start=clock();
            input_debug(i);
            ll cost=solve();
            ll score=1e9/(1000+sqrt(cost));
            scoresum+=score;
            cout << score << endl;
        }
        cout << scoresum << endl;
    }
    return 0;
}
0