結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 Michirakara
|
| 提出日時 | 2023-04-26 09:32:19 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 953 ms / 1,000 ms |
| コード長 | 9,920 bytes |
| コンパイル時間 | 2,587 ms |
| コンパイル使用メモリ | 203,284 KB |
| 実行使用メモリ | 4,372 KB |
| スコア | 8,661,947 |
| 最終ジャッジ日時 | 2023-04-26 09:32:54 |
| 合計ジャッジ時間 | 34,678 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 952 ms
4,372 KB |
| testcase_01 | AC | 952 ms
4,372 KB |
| testcase_02 | AC | 952 ms
4,368 KB |
| testcase_03 | AC | 952 ms
4,372 KB |
| testcase_04 | AC | 952 ms
4,372 KB |
| testcase_05 | AC | 952 ms
4,372 KB |
| testcase_06 | AC | 952 ms
4,368 KB |
| testcase_07 | AC | 952 ms
4,368 KB |
| testcase_08 | AC | 952 ms
4,368 KB |
| testcase_09 | AC | 953 ms
4,368 KB |
| testcase_10 | AC | 952 ms
4,372 KB |
| testcase_11 | AC | 952 ms
4,368 KB |
| testcase_12 | AC | 952 ms
4,372 KB |
| testcase_13 | AC | 952 ms
4,372 KB |
| testcase_14 | AC | 952 ms
4,372 KB |
| testcase_15 | AC | 952 ms
4,372 KB |
| testcase_16 | AC | 952 ms
4,368 KB |
| testcase_17 | AC | 953 ms
4,368 KB |
| testcase_18 | AC | 952 ms
4,368 KB |
| testcase_19 | AC | 952 ms
4,368 KB |
| testcase_20 | AC | 952 ms
4,372 KB |
| testcase_21 | AC | 952 ms
4,368 KB |
| testcase_22 | AC | 953 ms
4,372 KB |
| testcase_23 | AC | 952 ms
4,368 KB |
| testcase_24 | AC | 952 ms
4,372 KB |
| testcase_25 | AC | 952 ms
4,368 KB |
| testcase_26 | AC | 952 ms
4,368 KB |
| testcase_27 | AC | 952 ms
4,368 KB |
| testcase_28 | AC | 952 ms
4,368 KB |
| testcase_29 | AC | 952 ms
4,368 KB |
コンパイルメッセージ
main.cpp:8:9: 警告: #pragma once がメインファイルにあります
8 | #pragma once
| ^~~~
ソースコード
/**************************************************/
/*
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);
double temp=start_temp+(end_temp-start_temp)*time/end_time;
double prob=exp((GetDist(P[l-1],P[l])+GetDist(P[r],P[(r+1)%sz(P)]))-(GetDist(P[l-1],P[r])+GetDist(P[l],P[(r+1)%sz(P)])))/temp;
if(Randouble()<prob){
reverse(P.begin()+l,P.begin()+r+1);
score_now=GetScore(P);
}
//間に宇宙ステーションを入れるか
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;
}
}
prob=exp((GetDist(P[ind],P[(ind+1)%sz(P)]))-(GetDist(P[ind],-mi-1)+GetDist(-mi-1,P[(ind+1)%sz(P)])))/temp;
if(Randouble()<prob){
P.insert(P.begin()+ind+1,-mi-1);
score_now=GetScore(P);
}
//宇宙ステーションの場所移動
ind=RandInt(0,8);
int dx=RandInt(-20,20),dy=RandInt(-20,20);
if(!(X2[ind]+dx<0 || 1000<=X2[ind]+dx || Y2[ind]+dy<0 || 1000<=Y2[ind]+dy)){
X2[ind]+=dx,Y2[ind]+=dy;
ll 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;
}