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

• 問題: No.5007 Steiner Space Travel
• ユーザー: Kahuka
• 提出日時: 2023-04-23 13:40:51
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 934 ms / 1,000 ms
• コード長: 8,162 bytes
• コンパイル時間: 3,025 ms
• コンパイル使用メモリ: 210,212 KB
• 実行使用メモリ: 4,372 KB
• スコア: 8,876,944
• 最終ジャッジ日時: 2023-04-23 13:41:25
• 合計ジャッジ時間: 34,403 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

ファイルパターン	結果
other	AC * 30

ソースコード

#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) cout << i << " ";cout << endl;}
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define errve(v) {for(auto i : v) cout << i << " ";cout << endl;}
#define errmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << 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);}


double TIME_LIMIT = 0.9;
int LOCAL = 0;
int TEATER = 0;


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 Timer {
    int ti;
    double time;
public:
    Timer(){}
    void start(){ti = clock();}
    inline double get_time(){return time = (LOCAL==1 ? 2.0 : 1.0) * (clock() - ti) / CLOCKS_PER_SEC;}
    inline double now(){return time;}
};


const int N = 100;
const int M = 8;
const int L = 1001;

class SimulatedAnnealing {

    Timer timer;
    ll score;

    int planet_x[N];
    int planet_y[N];
    int station_x[M];
    int station_y[M];
    vi order;
    int alpha = 5;
    
public:
    SimulatedAnnealing(){
        timer.start();
        int n,m;
        cin >> n >> m;
        rep(i,N) cin >> planet_x[i] >> planet_y[i];
        rep(i,M) station_x[i] = xorshift()%L, station_y[i] = xorshift()%L;
        
        score = 0;
    }
    
    ll cal_score(vi &ord){
        ll res = 0;
        rep(i,si(order)-1) res += cal_dist(ord[i],ord[i+1]);
        return 1000000000ll/(1000ll+(ll)sqrt(res));
    }
    
    ll cal_dist(int a, int b){
        int c = 0;
        int dx = 0, dy = 0;
        
        if(a >= N) a -= N, dx = station_x[a], dy = station_y[a];
        else c++, dx = planet_x[a], dy = planet_y[a];
        if(b >= N) b -= N, dx -= station_x[b], dy -= station_y[b];
        else c++, dx -= planet_x[b], dy -= planet_y[b];
        
        int aa = 1;
        rep(i,c) aa *= alpha;
        return ll(aa*(dx*dx+dy*dy));
    }
    
    void solve(){
        
        vi vis(N+M,0);
        vis[0] = 1;
        order.pb(0);
        rep(i,N+M){
            int id = -1;
            ll d = infl;
            rep(j,N+M) if(vis[j] == 0 && order.back() != j){
                if(chmin(d,cal_dist(order.back(),j))) id = j;
            }
            if(id == -1) break;
            order.pb(id);
            vis[id] = 1;
        }
        order.pb(0);
        
        score = cal_score(order);
        cerr << score<< endl;
        
        
        int loop = 0;
        double T1 = 600, T0 = 0;
        double T = T1;
        while (timer.now() < TIME_LIMIT) {
            loop++;
            
            ll score0 = score;
            vi order0;
            int station_x0[M],station_y0[M];
            
            int type = 0;
            int prob = xorshift()%100;
            if(prob < 6){
                
                type = 0;
                order0 = order;
                int n = xorshift()%((si(order))-2)+1;
                int m = xorshift()%((si(order))-2)+1;
                while (n == m) m = xorshift()%((si(order))-2)+1;
                if(n > m) swap(n,m);
                while (n < m) {
                    swap(order[n],order[m]);
                    n++, m--;
                }
                
                reps(a,1,si(order)-1) reps(b,a+1,si(order)-1){
                    if(cal_dist(order[a-1],order[a])+cal_dist(order[b],order[b+1]) > cal_dist(order[a-1],order[b])+cal_dist(order[a],order[b+1])){
                        int n = a, m = b;
                        while (n < m) {
                            swap(order[n],order[m]);
                            n++,m--;
                        }
                    }
                }
                
                
            }else if(prob < 90){
                
                type = 1;
                rep(i,M) station_x0[i] = station_x[i], station_y0[i] = station_y[i];
                int n = xorshift()%M;
                station_x[n] += xorshift()%200 * (xorshift()%2 == 0 ? -1 : 1);
                station_y[n] += xorshift()%200 * (xorshift()%2 == 0 ? -1 : 1);
                chmax(station_x[n],0);
                chmin(station_x[n],1000);
                chmax(station_y[n],0);
                chmin(station_y[n],1000);
                
            }else{
                
                type = 2;
                order0 = order;
                if(xorshift()%2 == 0){
                    
                    int n = xorshift()%(si(order)-2)+1;
                    order.insert(order.begin()+n, xorshift()%M+N);
                    
                }else{
                    
                    int n = xorshift()%(si(order)-2)+1;
                    rep(_,200) if(order[n] < N){
                        n = xorshift()%(si(order)-2)+1;
                    }
                    if(order[n] >= N) order.erase(order.begin()+n);
                    
                }
                
            }
            
            ll score1 = cal_score(order);
            if(score0 < score1){
                score = score1;
                
            }else{
                if((double)(xorshift()%infi)/(double)infi < exp((score1-score0)/T)){
                    score = score1;
                    
                }else{
                    if(type == 0 || type == 2) order = order0;
                    else if(type == 1) {
                        rep(i,M) station_x[i] = station_x0[i], station_y[i] = station_y0[i];
                    }
                }
            }
            
            timer.get_time();
            T = T1 + (T0-T1)*timer.now()/TIME_LIMIT;
            if(LOCAL && loop%1000 == 0) cerr << loop csp score csp timer.now() csp T << endl;
        }
        
        cerr << score csp timer.get_time()  << endl;
        print_ans();
    }
    
    void print_ans(){
        rep(i,M) cout << station_x[i] csp station_y[i] << endl;
        cout << si(order) << endl;
        rep(i,si(order)){
            if(order[i] < N) cout << 1 csp order[i]+1 << endl;
            else cout << 2 csp order[i]-N+1 << endl;
        }
    }
    
};


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


    SimulatedAnnealing solver;
    solver.solve();
    
    return 0;
}