#858724 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	Kahuka
提出日時	2023-04-13 01:00:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	936 ms / 1,000 ms
コード長	11,342 bytes
コンパイル時間	3,038 ms
コンパイル使用メモリ	228,436 KB
実行使用メモリ	4,372 KB
スコア	8,382,610
最終ジャッジ日時	2023-04-13 01:01:00
合計ジャッジ時間	33,516 ms
ジャッジサーバーID （参考情報）	judge13 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	931 ms 4,372 KB
testcase_01	AC	908 ms 4,368 KB
testcase_02	AC	908 ms 4,372 KB
testcase_03	AC	931 ms 4,372 KB
testcase_04	AC	930 ms 4,368 KB
testcase_05	AC	908 ms 4,372 KB
testcase_06	AC	908 ms 4,368 KB
testcase_07	AC	930 ms 4,368 KB
testcase_08	AC	930 ms 4,372 KB
testcase_09	AC	908 ms 4,368 KB
testcase_10	AC	907 ms 4,368 KB
testcase_11	AC	907 ms 4,372 KB
testcase_12	AC	907 ms 4,368 KB
testcase_13	AC	930 ms 4,368 KB
testcase_14	AC	930 ms 4,368 KB
testcase_15	AC	908 ms 4,368 KB
testcase_16	AC	908 ms 4,368 KB
testcase_17	AC	931 ms 4,368 KB
testcase_18	AC	931 ms 4,368 KB
testcase_19	AC	907 ms 4,368 KB
testcase_20	AC	907 ms 4,368 KB
testcase_21	AC	930 ms 4,372 KB
testcase_22	AC	931 ms 4,368 KB
testcase_23	AC	908 ms 4,372 KB
testcase_24	AC	907 ms 4,368 KB
testcase_25	AC	930 ms 4,372 KB
testcase_26	AC	936 ms 4,372 KB
testcase_27	AC	933 ms 4,372 KB
testcase_28	AC	930 ms 4,372 KB
testcase_29	AC	907 ms 4,368 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define reps(i,s,n) for(int i=s; i<n; i++)
#define per(i,n) for(int i=n-1; i>=0; i--)
#define pers(i,n,s) for(int i=n-1; i>=s; i--)
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define pb push_back
#define si(v) int(v.size())
#define lb(v,n) lower_bound(all(v),n)
#define lbi(v,n) int(lower_bound(all(v),n) - v.begin())
#define ub(v,n) upper_bound(all(v),n)
#define ubi(v,n) int(upper_bound(all(v),n) - v.begin())
 
#define mod 1000000007
#define infi 1010000000
#define infl 1100000000000000000
 
#define outve(v) {for(auto i : v) cerr << i << " ";cerr << endl;}
#define outmat(v) for(auto i : v){for(auto j : i) cerr << j << " ";cerr << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define IN(n,m,v) rep(i,n) rep(j,m){cin >> v[i][j];}
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define cYES cout << "YES" << endl
#define cNO cout << "NO" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
 
using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using vv = vector<vector<T>>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}

int popcnt(uint n) {return __builtin_popcount(n);}
int popcntl(ull n) {return __builtin_popcountll(n);}
int bsr(uint n) {return 31 - __builtin_clz(n);}
int bsrl(ull n) {return 63 - __builtin_clzll(n);}
int bsf(uint n) {return __builtin_ctz(n);}
int bsfl(ull n) {return __builtin_ctzll(n);}


const int LOCAL = 0;
double TIME_LIMIT = 0.9;


unsigned int xorshift() {
    static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123;
    unsigned int tt = (tx^(tx<<11));
    tx = ty; ty = tz; tz = tw;
    return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) );
}

class Solver {
    int N,M;
    vl planet_x,planet_y,station_x,station_y;
    ll alpha;
    int max_xy = 1001;
    
    int ti;
    double time;
    
    ll score;
    
    
public:
    Solver(){
        ti = clock();
        alpha = 5;
        cin >> N >> M;
        planet_x.resize(N);
        planet_y.resize(N);
        rep(i,N) cin >> planet_x[i] >> planet_y[i];
        station_x.assign(M,0);
        station_y.assign(M,0);
        score = -infl;
    }
    
    inline ll cal_dist(ll x0, ll y0, ll x1, ll y1){
        return (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0);
    }
    
    
    void solve(){
        
        time = 1.0 * (clock() - ti) / CLOCKS_PER_SEC;
        
        int loop = 0;
        rep(i,M) station_x[i] = xorshift()%max_xy, station_y[i] = xorshift()%max_xy;
        
        double T1 = 10000, T0 = 0;
        double T = T1;
        while(time < TIME_LIMIT){
            loop++;
            
            ll score0 = score;
            int change_n = xorshift()%M;
            int station_x0 = station_x[change_n];
            int station_y0 = station_y[change_n];
            int dd = 500 + (40-500)/TIME_LIMIT*time;
            int dx = xorshift()%dd*(xorshift()%2==0 ? -1:1), dy = xorshift()%dd*(xorshift()%2==0 ? -1:1);
            station_x[change_n] += dx,station_y[change_n] += dy;
            chmin(station_x[change_n],1000ll), chmin(station_y[change_n],1000ll);
            chmax(station_x[change_n],0ll), chmax(station_y[change_n],0ll);
            
            vi neigbor(N,-1);
            vl d_planet_station(N,0);
            rep(i,N){
                ll d = infl;
                rep(j,M) if(chmin(d, cal_dist(station_x[j],station_y[j],planet_x[i],planet_y[i]))) neigbor[i] = j;
                d_planet_station[i] = d;
            }
            
            vvl D(M,vl(M,0));
            rep(i,M) reps(j,i+1,M) D[i][j] = D[j][i] = cal_dist(station_x[i],station_y[i],station_x[j],station_y[j]);
            vvl dp(int(1<<M),vl(M,infl));
            rep(i,M) if(i != neigbor[0]) dp[int(1<<i)][i] = D[neigbor[0]][i];
            rep(b,int(1<<M)){
                rep(j,M)if(b & 1 << j){
                    rep(k,M) if(!(b&1<<k)) chmin(dp[int(b|1<<k)][k],dp[b][j]+D[j][k]);
                }
            }
            ll d_station = dp[int(1<<M)-1][neigbor[0]];
            ll score1 = d_station;
            
            rep(i,M){
                vi P;
                rep(j,N) if(neigbor[j] == i) P.pb(j);
                if(si(P) == 0) continue;
                
                vi I;
                rep(i,si(P)) I.pb(i);
                sort(all(I),[&](int a, int b){
                    return atan2(planet_x[P[a]]-station_x[i],planet_y[P[a]]-station_y[i]) < atan2(planet_x[P[b]]-station_x[i],planet_y[P[b]]-station_y[i]);
                });
                
                
                int s = 0;
                ll ddd = infl;
                rep(ii,si(I)){
                    int i = I[ii];
                    if(chmin(ddd,d_planet_station[P[i]])) s = ii;
                    if(P[i] == 0) {
                        s = ii;
                        break;
                    }
                }
                
                ll d = d_planet_station[P[I[s]]]*alpha;
                rep(iii,si(I)){
                    if(iii == si(I)-1){
                        int p0 = P[I[(iii+s)%si(P)]];
                        int p1 = P[I[(iii+s+1)%si(P)]];
                        if(d_planet_station[p0]*alpha > cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha+d_planet_station[p1]*alpha){
                            d += cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha + d_planet_station[p1]*alpha;
                        }else{
                            d += d_planet_station[p0]*alpha;
                        }
                        break;
                    }
                    int p0 = P[I[(iii+s)%si(P)]];
                    int p1 = P[I[(iii+s+1)%si(P)]];
                    if((d_planet_station[p0]+d_planet_station[p1])*alpha > cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha){
                        d += cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha;
                    }else{
                        d += (d_planet_station[p0]+d_planet_station[p1])*alpha;
                    }
                }
                score1 += d;
            }
            
            
            score1 = ll(1000000000.0/(1000.0+sqrt(double(score1))));
            
            if(score0 < score1){
                score = score1;
            }else{
                if((double)(xorshift()%infi)/(double)infi < exp((score1-score0)/T)){
                    score = score1;
                }else{
                    station_x[change_n] = station_x0;
                    station_y[change_n] = station_y0;
                }
            }
            time = 1.0 * (clock() - ti) / CLOCKS_PER_SEC;
            if(LOCAL) time *= 2;
            T = T1 + (T0-T1)/(TIME_LIMIT) * (time);
            if(LOCAL && loop%100 == 0) cerr << loop csp score csp score1  csp time csp T << endl;
        }
        
        time =  1.0 * (clock() - ti) / CLOCKS_PER_SEC;
        if(LOCAL) cerr << loop csp score csp time << endl;
        
        print_ans();
    }
    
    
    
    
    
    void print_ans(){
        rep(i,M) cout << station_x[i] csp station_y[i] << endl;
        
        vi t,r;
        
        vi neigbor(N,-1);
        vl d_planet_station(N,0);
        rep(i,N){
            ll d = infl;
            rep(j,M) if(chmin(d, cal_dist(station_x[j],station_y[j],planet_x[i],planet_y[i]))) neigbor[i] = j;
            d_planet_station[i] = d;
        }
        
        vvl D(M,vl(M,0));
        rep(i,M) reps(j,i+1,M) D[i][j] = D[j][i] = cal_dist(station_x[i],station_y[i],station_x[j],station_y[j]);
        vvl dp(int(1<<M),vl(M,infl));
        vvi from(int(1<<M),vi(M,-1));
        rep(i,M) if(i != neigbor[0]) dp[int(1<<i)][i] = D[neigbor[0]][i], from[int(1<<i)][i] = neigbor[0];
        rep(b,int(1<<M)){
            rep(j,M) if(b & 1 << j){
                rep(k,M) if(!(b&1<<k)) if(chmin(dp[int(b|1<<k)][k],dp[b][j]+D[j][k])) from[int(b|1<<k)][k] = j;
            }
        }
        vi station_ord;
        int bit = int(1<<M)-1;
        int s = neigbor[0];
        while(from[bit][s] >= 0){
            int s0 = s;
            s = from[bit][s];
            station_ord.pb(s);
            bit ^= int(1<<s0);
        }
        reverse(all(station_ord));
        t.pb(1);
        r.pb(0);
        
        for (int station : station_ord) {
            
            vi P;
            rep(j,N) if(neigbor[j] == station) P.pb(j);
            if(si(P) == 0) continue;
            
            vi I;
            rep(i,si(P)) I.pb(i);
            sort(all(I),[&](int a, int b){
                return atan2(planet_x[P[a]]-station_x[station],planet_y[P[a]]-station_y[station]) < atan2(planet_x[P[b]]-station_x[station],planet_y[P[b]]-station_y[station]);
            });
            
            int s = 0;
            int f = 0;
            ll ddd = infl;
            rep(ii,si(I)){
                int i = I[ii];
                if(chmin(ddd,d_planet_station[P[i]])) s = ii;
                if(P[i] == 0) {
                    s = ii;
                    f = 1;
                    break;
                }
            }
            if(f == 0){
                t.pb(2);
                r.pb(station);
                t.pb(1);
                r.pb(P[I[s]]);
            }
            rep(iii,si(I)){
                if(iii == si(I)-1){
                    int p0 = P[I[(iii+s)%si(P)]];
                    int p1 = P[I[(iii+s+1)%si(P)]];
                    if(d_planet_station[p0]*alpha > cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha+d_planet_station[p1]*alpha){
                        t.pb(1);
                        r.pb(p1);
                        t.pb(2);
                        r.pb(station);
                    }else{
                        t.pb(2);
                        r.pb(station);
                    }
                    break;
                }
            
                int p0 = P[I[(iii+s)%si(P)]];
                int p1 = P[I[(iii+s+1)%si(P)]];
                if((d_planet_station[p0]+d_planet_station[p1])*alpha > cal_dist(planet_x[p0],planet_y[p0],planet_x[p1],planet_y[p1])*alpha*alpha){
                    t.pb(1);
                    r.pb(p1);
                }else{
                    t.pb(2);
                    r.pb(station);
                    t.pb(1);
                    r.pb(p1);
                }
            }
        }
        t.pb(2);
        r.pb(neigbor[0]);
        t.pb(1);
        r.pb(0);
        cout << si(r) << endl;
        rep(i,si(r)) cout << t[i] csp r[i]+1 << endl;
    }
};


int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Solver solver;
    solver.solve();
    

    return 0;
}

yukicoder

結果

テストケース

ソースコード