結果

問題 No.5007 Steiner Space Travel
ユーザー KahukaKahuka
提出日時 2023-04-12 22:06:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 954 ms / 1,000 ms
コード長 7,405 bytes
コンパイル時間 2,907 ms
コンパイル使用メモリ 217,100 KB
実行使用メモリ 4,372 KB
スコア 7,264,776
最終ジャッジ日時 2023-04-12 22:06:47
合計ジャッジ時間 34,668 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 907 ms
4,368 KB
testcase_01 AC 931 ms
4,372 KB
testcase_02 AC 954 ms
4,368 KB
testcase_03 AC 931 ms
4,372 KB
testcase_04 AC 908 ms
4,372 KB
testcase_05 AC 907 ms
4,368 KB
testcase_06 AC 930 ms
4,368 KB
testcase_07 AC 930 ms
4,368 KB
testcase_08 AC 906 ms
4,372 KB
testcase_09 AC 931 ms
4,372 KB
testcase_10 AC 930 ms
4,368 KB
testcase_11 AC 930 ms
4,372 KB
testcase_12 AC 908 ms
4,368 KB
testcase_13 AC 931 ms
4,372 KB
testcase_14 AC 907 ms
4,372 KB
testcase_15 AC 931 ms
4,368 KB
testcase_16 AC 929 ms
4,372 KB
testcase_17 AC 930 ms
4,368 KB
testcase_18 AC 907 ms
4,368 KB
testcase_19 AC 906 ms
4,368 KB
testcase_20 AC 931 ms
4,372 KB
testcase_21 AC 930 ms
4,372 KB
testcase_22 AC 907 ms
4,368 KB
testcase_23 AC 907 ms
4,372 KB
testcase_24 AC 930 ms
4,368 KB
testcase_25 AC 930 ms
4,368 KB
testcase_26 AC 907 ms
4,372 KB
testcase_27 AC 908 ms
4,368 KB
testcase_28 AC 931 ms
4,368 KB
testcase_29 AC 930 ms
4,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 = 1000, 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 = 1000 + (100-1000)/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);
            ll score1 = 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;
                score1 += d*2LL*alpha;
            }
            
            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]];
            score1 += d_station;
            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);
        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;
        }
        
        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));
        vi vis(N,0);
        t.pb(1);
        r.pb(0);
        vis[0] = 1;
        
        for (int station : station_ord) {
            t.pb(2);
            r.pb(station);
            rep(i,N) if(neigbor[i] == station && vis[i] == 0){
                vis[i] = 1;
                t.pb(1);
                r.pb(i);
                t.pb(2);
                r.pb(station);
            }
        }
        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;
}
0