結果

問題 No.5007 Steiner Space Travel
ユーザー MichirakaraMichirakara
提出日時 2023-04-24 03:27:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 805 ms / 1,000 ms
コード長 9,010 bytes
コンパイル時間 2,682 ms
コンパイル使用メモリ 203,536 KB
実行使用メモリ 4,372 KB
スコア 8,044,679
最終ジャッジ日時 2023-04-24 03:28:03
合計ジャッジ時間 29,809 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 802 ms
4,368 KB
testcase_01 AC 802 ms
4,368 KB
testcase_02 AC 802 ms
4,368 KB
testcase_03 AC 802 ms
4,372 KB
testcase_04 AC 802 ms
4,368 KB
testcase_05 AC 803 ms
4,372 KB
testcase_06 AC 801 ms
4,372 KB
testcase_07 AC 802 ms
4,368 KB
testcase_08 AC 802 ms
4,368 KB
testcase_09 AC 805 ms
4,372 KB
testcase_10 AC 802 ms
4,372 KB
testcase_11 AC 801 ms
4,368 KB
testcase_12 AC 803 ms
4,372 KB
testcase_13 AC 802 ms
4,368 KB
testcase_14 AC 802 ms
4,372 KB
testcase_15 AC 802 ms
4,368 KB
testcase_16 AC 802 ms
4,372 KB
testcase_17 AC 802 ms
4,372 KB
testcase_18 AC 802 ms
4,368 KB
testcase_19 AC 801 ms
4,372 KB
testcase_20 AC 803 ms
4,368 KB
testcase_21 AC 802 ms
4,372 KB
testcase_22 AC 802 ms
4,368 KB
testcase_23 AC 803 ms
4,368 KB
testcase_24 AC 802 ms
4,368 KB
testcase_25 AC 801 ms
4,368 KB
testcase_26 AC 802 ms
4,368 KB
testcase_27 AC 802 ms
4,372 KB
testcase_28 AC 802 ms
4,372 KB
testcase_29 AC 802 ms
4,372 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:9: 警告: #pragma once がメインファイルにあります
    8 | #pragma once
      |         ^~~~

ソースコード

diff # 

/**************************************************/
/*
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<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;

//[a,b)
int RandInt(int a,int b){
    return rand()%(b-a)+a;
}
double Randouble(){
    return 1.0*rand()/RAND_MAX;
}

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];

    int ind=0;

    vi tmpx={250,250,250,500,500,750,750,750};
    vi tmpy={250,500,750,333,666,250,500,750};
    rep(i,8){
        X2[i]=tmpx[i];
        Y2[i]=tmpy[i];
        print(tmpx[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.8;
    double time=0.0;
    do{
        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);
        }
        time=(duration_cast<microseconds>(system_clock::now()-start_clock).count()*1e-6);
    }while(time<end_time);

    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<<1E9/(1000+sqrt(GetScore(P)))<<endl;
}
0