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

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	Michirakara
提出日時	2023-04-25 23:54:15
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	953 ms / 1,000 ms
コード長	9,940 bytes
コンパイル時間	2,846 ms
コンパイル使用メモリ	203,944 KB
実行使用メモリ	4,372 KB
スコア	8,616,209
最終ジャッジ日時	2023-04-25 23:54:53
合計ジャッジ時間	34,496 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語

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

テストケース

テストケース表示

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

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

コンパイルメッセージ

main.cpp:8:9: 警告: #pragma once がメインファイルにあります
    8 | #pragma once
      |         ^~~~

ソースコード

raw source code

/**************************************************/
/*
C++ template 
    by michirakara
    「嘘解法は友達」(?)
*/
//include std
#pragma once
#include <cassert>
#include <cfenv>
#include <cfloat>
#include <ciso646>
#include <clocale>
#include <csetjmp>
#include <csignal>
#include <cstdbool>
#include <cinttypes>
#include <charconv>
#include <typeindex>
#include <any>
#include <scoped_allocator>
#include <forward_list>
#include <list>
#include <map>
#include <set>
#include <valarray>
#include <variant>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <condition_variable>
#include <shared_mutex>
#include <codecvt>
#include <future>
#include <regex>
#include <iostream>
#include <random>
#include <ctgmath>
#include <fstream>
#include<climits>
#include<chrono>
using namespace std;
using namespace chrono;

//コンパイラと浮動小数点高速化
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

//cin,endlの高速化
//インタラクティブのときは外す
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
#define endl '\n'

//using
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
using vvi=vector<vi>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;//PLLはY-permが好き

const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=998244353;
const ld PI=3.1415926535897932384626433832795028841971;

const ll dx[]={0,1,0,-1};
const ll dy[]={1,0,-1,0};
const ll dx8[]={0,1,0,-1,1,-1,1,-1};
const ll dy8[]={1,0,-1,0,1,1,-1,-1};

//define
#define itn int//これすき

#define elif else if

/*最終兵器
絶対使うな
#define int long long
*/
 
//マクロ

//min(a,b,....)-> min({a,b,....})
//Pythonのように任意個の要素を入れることの可能なmin()
template<class... T>
constexpr auto min(T... a){
    return min(initializer_list<common_type_t<T...>>{a...});
}
//同じくmax
template<class... T>
constexpr auto max(T... a){
    return max(initializer_list<common_type_t<T...>>{a...});
}

void scan(int& a){cin>>a;}
void scan(unsigned& a){cin>>a;}
void scan(long& a){cin>>a;}
void scan(long long& a){cin>>a;}
void scan(unsigned long long& a){cin>>a;}
void scan(float& a){cin>>a;}
void scan(double& a){cin>>a;}
void scan(long double& a){cin>>a;}
void scan(char& a){cin>>a;}
void scan(string& a){cin>>a;}
template<class T> void scan(vector<T>&);
template<class T,size_t size> void scan(array<T,size>&);
template<class T,class L> void scan(pair<T,L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){for(auto&& i:a)scan(i);};
template<class T> void scan(deque<T>& a){for(auto&& i:a)scan(i);};
template<class T,size_t size> void scan(array<T,size>& a){for(auto&& i:a)scan(i);};
template<class T,class L> void scan(pair<T,L>& a){scan(a.first);scan(a.second);};
template<class T, size_t size> void scan(T(&a)[size]){for(auto&& i:a)scan(i);};
template<class T> void scan(T& a){cin>>a;}
void input(){}
//input(a,b...)-> cin>>a>>b>>...
//input(変数名...)で勝手に入力を受け取ってくれる かしこい
template<class Head,class... Tail>
void input(Head& H,Tail&... T){
    scan(H);input(T...);
}

//INT(a,b)-> int a,b;cin>>a>>b;
//INT(変数名)でintの変数を作ってinputから取ってくれる かしこい
#define INT(...)int __VA_ARGS__; input(__VA_ARGS__)
//LL(a,b)-> long long a,b;cin>>a>>b;
//LL(変数名)でllの変数を作ってinputから取ってくれる かしこい
#define LL(...)ll __VA_ARGS__; input(__VA_ARGS__)

void puts(){cout<<' ';}
void puts(int a){cout<<a;}
void puts(unsigned a){cout<<a;}
void puts(long a){cout<<a;}
void puts(long long a){cout<<a;}
void puts(unsigned long long a){cout<<a;}
void puts(float a){cout<<a;}
void puts(double a){cout<<a;}
void puts(long double a){cout<<a;}
void puts(char a){cout<<a;}
void puts(string a){cout<<a;}
template<class T> void puts(vector<T>);
template<class T,size_t size> void puts(array<T,size>);
template<class T,class L> void puts(pair<T,L>);
template<class T, size_t size> void puts(T[size]);
template<class T> void puts(vector<T> a){if(a.empty())return;puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T> void puts(deque<T> a){if(a.empty())return;puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T,size_t size> void puts(array<T,size> a){puts(a[0]);for(auto i=a.begin();++i!=a.end();){cout<<' ';puts(*i);}};
template<class T,class L> void puts(pair<T,L> a){puts(a.first);cout<<' ';puts(a.second);};
template<class T, size_t size> void puts(T(a)[size]){puts(a[0]);for(auto i=a;++i!=end(a);){cout<<' ';puts(*i);}};
template<class T> void puts(T a){cout<<a;}
void print(){cout<<endl;}
//print(a,b...)ほぼPythonのprintといっしょ <- うれしい
template<class Head,class... Tail>
void print(Head H,Tail... T){
    puts(H);print(T...);
}

//rep1(i,a)-> i in [0,a)
//reps(i,a,b)-> i in [a,b)
//r_p(i,a,b,c)-> i in [a,b) by c
#define rep1(i, a) for(ll i=0; i<(ll)a; i++)
#define reps(i, a, b) for(ll i=a; i<(ll)b; i++)
#define r_p(i, a, b, c) for(ll i=a; i<(ll)b; i+=c)

//rep(i,a)-> i in [0,a)
//rep(i,a,b)-> i in [a,b)
//rep(i,a,b,c)-> i in [a,b) by c
//大体Pythonのfor文と同じrepマクロ
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, r_p, reps, rep1)(__VA_ARGS__)

//イテレータの最初から最後までを返す 例:sort(all(v))
#define all(x) (x).begin(),(x).end()
//上の逆順 例:sort(rall(v)) (降順にソートされる)
#define rall(x) (x).rbegin(),(x).rend()

//next_permutationでもらえる順に全部順列を返す 例:for(vi i:perm(v))
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

//sizeを int(ここ大事) で返す
#define sz(x) ((int)(x).size())

//boolを渡すとYesNoを出力する
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
/**************************************************/
int N,M,X[100],Y[100],X2[8],Y2[8];
int A=5;

static uint32_t randXor()
{
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t;

    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

//[a,b)
int RandInt(int a,int b){
    return randXor()%(b-a)+a;
}
double Randouble(){
    return (randXor() + 0.5) * (1.0 / 0xffffffff);
}

ll GetDist(int fi,int si){
    if(fi>=0){
        if(si>=0){
            return (pow((X[fi]-X[si]),2)+pow((Y[fi]-Y[si]),2))*A*A;
        }else{
            return (pow((X[fi]-X2[~si]),2)+pow((Y[fi]-Y2[~si]),2))*A;
        }
    }else{
        if(si>=0){
            return (pow((X2[~fi]-X[si]),2)+pow((Y2[~fi]-Y[si]),2))*A;
        }else{
            return (pow((X2[~fi]-X2[~si]),2)+pow((Y2[~fi]-Y2[~si]),2));
        }
    }
}

ll GetScore(vi &P){
    ll res=0;
    rep(i,sz(P)){
        res+=GetDist(P[i],P[(i+sz(P)-1)%sz(P)]);
    }
    return res;
}

int main(){
    input(N,M);
    rep(i,N)cin>>X[i]>>Y[i];


    vi tmpy={250,250,250,500,500,750,750,750};
    vi tmpx={250,500,750,333,666,250,500,750};
    rep(i,8){
        X2[i]=tmpx[i];
        Y2[i]=tmpy[i];
    }

    //初期解の作成
    vector<bool> gone(N,false);
    gone[0]=true;
    vi P={0};
    int nx=X[0],ny=Y[0];
    rep(i,1,N){
        int mi=INF;
        int to=-1;
        rep(j,N){
            if(gone[j])continue;
            int tmp=(nx-X[j])*(nx-X[j])+(ny-Y[j])*(ny-Y[j]);
            if(tmp<mi){
                mi=tmp;
                to=j;
            }
        }
        gone[to]=true;
        nx=X[to],ny=Y[to];
        P.push_back(to);
    }
    cerr<<1E9/(1000+sqrt(GetScore(P)))<<endl;

    //やきなまし
    ll score_now=GetScore(P);
    double start_temp=10000;
    double end_temp=1000;
    auto start_clock=system_clock::now();
    double end_time=0.95;
    double time=0.0;

    int cnt=0;
    do{
        cnt++;
        //2-opt
        int l=RandInt(1,sz(P));
        int r=RandInt(1,sz(P));
        if(l>r)swap(l,r);
        reverse(P.begin()+l,P.begin()+r+1);
        
        ll score_new=GetScore(P);
        double temp=start_temp+(end_temp-start_temp)*time/end_time;
        double prob=exp(score_now-score_new)/temp;
        if(Randouble()<prob){
            score_now=score_new;
        }else{
            reverse(P.begin()+l,P.begin()+r+1);
        }

        //間に宇宙ステーションを入れるか
        int ind=RandInt(1,sz(P));

        int mi=-1,near=INF;
        rep(i,8){
            if(near>GetDist(P[ind],-i-1)){
                near=GetDist(P[ind],-i-1);
                mi=i;
            }
        }
        P.insert(P.begin()+ind,-mi-1);
        score_new=GetScore(P);
        prob=exp(score_now-score_new)/temp;
        if(Randouble()<prob){
            score_now=score_new;
        }else{
            P.erase(P.begin()+ind);
        }

        //宇宙ステーションの場所移動
        ind=RandInt(0,8);
        int dx=RandInt(-100,100),dy=RandInt(-100,100);
        if(!(X2[ind]+dx<0 || 1000<=X2[ind]+dx || Y2[ind]+dy<0 || 1000<=Y2[ind]+dy)){
            X2[ind]+=dx,Y2[ind]+=dy;
            score_new=GetScore(P);
            prob=exp(score_now-score_new)/(temp/5);
            if(Randouble()<prob){
                score_now=score_new;
            }else{
                X2[ind]-=dx,Y2[ind]-=dy;
            }
        }
        time=(duration_cast<microseconds>(system_clock::now()-start_clock).count()*1e-6);
    }while(time<end_time);

    rep(i,8){
        print(X2[i],' ',Y2[i]);
    }

    print(P.size()+1);
    rep(i,P.size()){
        if(P[i]>=0){
            print(1,' ',P[i]+1);
        }else{
            print(2,' ',-P[i]);
        }
    }
    print(1,' ',1);
    cerr<<cnt<<' '<<1E9/(1000+sqrt(GetScore(P)))<<endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード