結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 hari64
|
| 提出日時 | 2022-07-30 18:20:11 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 242 ms / 1,000 ms |
| コード長 | 25,841 bytes |
| コンパイル時間 | 3,299 ms |
| 実行使用メモリ | 14,340 KB |
| スコア | 6,926,732 |
| 最終ジャッジ日時 | 2022-07-30 18:20:22 |
| 合計ジャッジ時間 | 9,491 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 88 ms
8,544 KB |
| testcase_01 | AC | 162 ms
14,252 KB |
| testcase_02 | AC | 242 ms
14,340 KB |
| testcase_03 | AC | 99 ms
8,804 KB |
| testcase_04 | AC | 127 ms
13,800 KB |
| testcase_05 | AC | 118 ms
13,980 KB |
| testcase_06 | AC | 205 ms
13,900 KB |
| testcase_07 | AC | 130 ms
13,756 KB |
| testcase_08 | AC | 157 ms
14,304 KB |
| testcase_09 | AC | 149 ms
13,904 KB |
| testcase_10 | AC | 49 ms
5,856 KB |
| testcase_11 | AC | 177 ms
14,184 KB |
| testcase_12 | AC | 135 ms
13,952 KB |
| testcase_13 | AC | 193 ms
14,280 KB |
| testcase_14 | AC | 128 ms
13,932 KB |
| testcase_15 | AC | 138 ms
13,876 KB |
| testcase_16 | AC | 137 ms
13,852 KB |
| testcase_17 | AC | 97 ms
8,928 KB |
| testcase_18 | AC | 219 ms
13,952 KB |
| testcase_19 | AC | 111 ms
8,952 KB |
| testcase_20 | AC | 116 ms
13,908 KB |
| testcase_21 | AC | 203 ms
14,328 KB |
| testcase_22 | AC | 159 ms
14,240 KB |
| testcase_23 | AC | 133 ms
13,908 KB |
| testcase_24 | AC | 141 ms
14,304 KB |
| testcase_25 | AC | 178 ms
13,992 KB |
| testcase_26 | AC | 192 ms
14,228 KB |
| testcase_27 | AC | 197 ms
14,248 KB |
| testcase_28 | AC | 97 ms
8,688 KB |
| testcase_29 | AC | 142 ms
14,252 KB |
コンパイルメッセージ
main.cpp:28: 警告: "assert" が再定義されました
28 | #define assert(...)
|
次のファイルから読み込み: /usr/local/gcc7/include/c++/11.2.0/cassert:44,
次から読み込み: /usr/local/gcc7/include/c++/11.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:33,
次から読み込み: main.cpp:1:
/usr/include/assert.h:89: 備考: ここが以前の宣言がある位置です
89 | # define assert(expr) \
|
ソースコード
#include <bits/stdc++.h> // clang-format off
using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{using s=string;template<class T>s f(T i){s S=i==INF||i==INFll?"inf":to_string(i);return s(max(0,3-int(S.size())),' ')+S;}
template<class T>auto v(T&x,s&&e)->decltype(cerr<<x){return cerr<<x<<e;}void v(int x,s&&e){cerr<<f(x)<<e;}void v(long long x,s&&e){cerr<<f(x)<<e;}void v(float x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(long double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}
template<class T,class U>void v(const pair<T,U>&p,s&&e="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+e);}template<class T,class U>void v(const tuple<T,U>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),")"+e);}template<class T,class U,class V>void v(const tuple<T,U,V>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),")"+e);}template<class T,class U,class V,class W>void v(const tuple<T,U,V,W>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),", ");v(get<3>(t),")"+e);}
template<class T>void v(const vector<T>&vx,s);template<class T>auto ve(int,const vector<T>&vx)->decltype(cerr<<vx[0]){cerr<<"{";for(const T&x:vx)v(x,",");return cerr<<"}\n";}template<class T>auto ve(bool,const vector<T>&vx){cerr<<"{\n";for(const T&x:vx)cerr<<" ",v(x,",");cerr<<"}\n";}template<class T>void v(const vector<T>&vx,s){ve(0,vx);}
template<class T>void v(const deque<T>&q,s&&e){v(vector<T>(q.begin(),q.end()),e);}template<class T,class C>void v(const set<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T,class C>void v(const multiset<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T>void v(const unordered_set<T>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}
template<class T,class U,class V>void v(const priority_queue<T,U,V>&p,s&&e){priority_queue<T,U,V>q=p;vector<T>z;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);}template<class T,class U>void v(const map<T,U>&m,s&&e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<" [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;}
template<class T>void _view(int n,s&S,T&var){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S<<"\033[0m = ";v(var,"\n");}template<class T>void grid(T _){}void grid(const vector<vector<bool>>&vvb){cerr<<"\n";for(const vector<bool>&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}}
void _debug(int,s){}template<typename H,typename... T>void _debug(int n,s S,const H&h,const T&... t){int i=0,cnt=0;for(;i<int(S.size());i++){if(S[i]=='(')cnt++;if(S[i]==')')cnt--;if(cnt==0&&S[i]==',')break;}if(i==int(S.size()))_view(n,S,h);else{s S1=S.substr(0,i),S2=S.substr(i+2);if(S2=="\"grid\""){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S1<<"\033[0m = ";grid(h);}else _view(n,S1,h),_debug(n,S2,t...);}}}
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;} // https://rsk0315.hatenablog.com/entry/2021/01/18/065720
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
#ifndef hari64
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define assert(...)
#define debug(...)
#else
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif
struct Timer{
void start(){_start=chrono::system_clock::now();}
void stop(){_end=chrono::system_clock::now();sum+=chrono::duration_cast<chrono::nanoseconds>(_end-_start).count();}
inline int ms()const{const chrono::system_clock::time_point now=chrono::system_clock::now();return static_cast<int>(chrono::duration_cast<chrono::microseconds>(now-_start).count()/1000);}
inline int ns()const{const chrono::system_clock::time_point now=chrono::system_clock::now();return static_cast<int>(chrono::duration_cast<chrono::microseconds>(now-_start).count());}
string report(){return to_string(sum/1000000)+"[ms]";}
void reset(){_start=chrono::system_clock::now();sum=0;}
private: chrono::system_clock::time_point _start,_end;long long sum=0;
}timer;
struct Xor128{// period 2^128 - 1
uint32_t x,y,z,w;
static constexpr uint32_t min(){return 0;}
static constexpr uint32_t max(){return UINT32_MAX;}
Xor128(uint32_t seed=0):x(123456789),y(362436069),z(521288629),w(88675123+seed){}
uint32_t operator()(){uint32_t t=x^(x<<11);x=y;y=z;z=w;return w=(w^(w>>19))^(t^(t>>8));}
uint32_t operator()(uint32_t l,uint32_t r){return((*this)()%(r-l))+l;}
uint32_t operator()(uint32_t r){return(*this)()%r;}};
struct Rand{// https://docs.python.org/ja/3/library/random.html
Rand(){};
Rand(int seed):gen(seed){};
// シードを変更します
inline void set_seed(int seed){Xor128 _gen(seed);gen=_gen;}
// ランダムな浮動小数点数（範囲は[0.0, 1.0)) を返します
inline double random(){return(double)gen()/(double)gen.max();}
// a <= b であれば a <= N <= b 、b < a であれば b <= N <= a であるようなランダムな浮動小数点数 N を返します
inline double uniform(double a,double b){if(b<a)swap(a,b);return a+(b-a)*double(gen())/double(gen.max());}
// range(0, stop) の要素からランダムに選ばれた要素を返します
inline uint32_t randrange(uint32_t r){return gen(r);}
// range(start, stop) の要素からランダムに選ばれた要素を返します
inline uint32_t randrange(uint32_t l,uint32_t r){return gen(l,r);}
// a <= N <= b であるようなランダムな整数 N を返します randrange(a, b + 1) のエイリアスです
inline uint32_t randint(uint32_t l,uint32_t r){return gen(l,r+1);}
// シーケンス x をインプレースにシャッフルします
template<class T>void shuffle(vector<T>&x){for(int i=x.size(),j;i>1;){j=gen(i);swap(x[j],x[--i]);}}
// 空でないシーケンス seq からランダムに要素を返します
template<class T>T choice(const vector<T>&seq){assert(!seq.empty());return seq[gen(seq.size())];}
// 相対的な重みに基づいて要素が選ばれます (※複数回呼ぶ場合は処理を変えた方が良い)
template<class T,class U>T choice(const vector<T>&seq,const vector<U>&weights){assert(seq.size()==weights.size());vector<U>acc(weights.size());acc[0]=weights[0];for(int i=1;i<int(weights.size());i++)acc[i]=acc[i-1]+weights[i];return seq[lower_bound(acc.begin(),acc.end(),random()*acc.back())-acc.begin()];}
// 母集団のシーケンスまたは集合から選ばれた長さ k の一意な要素からなるリストを返します 重複無しのランダムサンプリングに用いられます
template<class T>vector<T>sample(const vector<T>&p,int k){int j,i=0,n=p.size();assert(0<=k&&k<=n);vector<T>ret(k);unordered_set<int>s;for(;i<k;i++){do{j=gen(n);}while(s.find(j)!=s.end());s.insert(j);ret[i]=p[j];}return ret;}
// 正規分布です mu は平均で sigma は標準偏差です
double normalvariate(double mu=0.0,double sigma=1.0){double u2,z,NV=4*exp(-0.5)/sqrt(2.0);while(true){u2=1.0-random();z=NV*(random()-0.5)/u2;if(z*z/4.0<=-log(u2))break;}return mu+z*sigma;}
private: Xor128 gen;
}myrand;
namespace esc{const vector<int>colors{196,208,226,46,77,14,12,13,5,136,195,245};constexpr int RED=0,ORANGE=1,YELLOW=2,LIGHTGREEN=3,GREEN=4,AQUA=5,BLUE=6,PINK=7,PURPLE=8,BROWN=9,WHITE=10,GRAY=11;
void back(int n){cerr<<"\e["<<n<<"A";}void locate(int r,int c){cerr<<"\e["<<r+1<<+";"<<c+1<<"H";}void reset(){cerr<<"\e[0m";}
void color(int c){cerr<<"\e[38;5;"<<colors[c]<<"m";}void color(int c,string s){color(c);cerr<<s;reset();}void color(int c,int s){color(c,to_string(s));}
void bcolor(int c){cerr<<"\e[4;"<<colors[c]<<"m";}void bcolor(int c,string s){bcolor(c);cerr<<s;reset();}void bcolor(int c,int s){color(c,to_string(s));}
string with_sep(int n,char sep=','){string ret="",s=to_string(n);reverse(s.begin(),s.end());for(int i=0,len=s.length();i<=len;){ret+=s.substr(i,3);if((i+=3)>=len)break;ret+=sep;}reverse(ret.begin(),ret.end());return ret;}
string with_fill(int n,int num=3,char space=' '){string s=to_string(n);return string(max(0,num-int(s.size())),space)+s;}
// **VISUALIZER-TEMPLATE**
// int N=20,M=30,vis_length=10;
// for(int vis_cnt=1;vis_cnt<=vis_length;vis_cnt++){cerr<<esc::with_fill(vis_cnt)<<"/"<<vis_length<<endl;cerr<<"";
// for(int x=0;x<M;x++)esc::color(esc::GRAY,x%10);cerr<<""<<endl;
// for(int y=0;y<N;y++){esc::color(esc::GRAY,y%10);esc::reset();
// for(int x=0;x<M;x++){/*wirte here*/esc::bcolor(y%10,myrand.randint(0,9));}esc::color(esc::GRAY,y%10);cerr<<endl;}cerr<<"";
// for(int x=0;x<M;x++)esc::color(esc::GRAY,x%10);cerr<<""<<endl;if(vis_cnt<vis_length)esc::back(N+2+1);usleep(1.0*1000000);}
}// namespace esc
// clang-format on
constexpr int N = 100; // 惑星の数
constexpr int M = 8; // 宇宙ステーションの数
constexpr long long alpha = 5;
vector<pair<long long, long long>> ABs(N, {0, 0});
vector<pair<long long, long long>> CDs(M, {0, 0});
inline long long dist(const pair<long long, long long>& p1,
const pair<long long, long long>& p2) {
return (p1.first - p2.first) * (p1.first - p2.first) +
(p1.second - p2.second) * (p1.second - p2.second);
};
// https://tsunelab-programming.com/alg-kmeans
auto k_means() {
//分類パターンの属するクラスタ番号
vector<int> iClassNum(N);
//各クラスタ中心初期位置
vector<pair<long long, long long>> dInitCenterPosit(M);
//各クラスタ中心位置
vector<pair<long long, long long>> dCenterPosit(M);
//合計値
vector<vector<long long>> dSum(M, vector<long long>(2, 0));
//クラスタに含まれる要素数
vector<int> iElemNum(M, 0);
//クラスタ中心位置と分類パターンの距離
vector<long long> dTempDistance(M);
/*
機能：最小距離クラスの決定
引数：int(クラス分類数) long long*(各クラスと対象パターンの距離)
戻値：最小距離となるクラスの番号
*/
auto fiClassDetermination = [&](int iClassNum,
vector<long long>& pdDist) -> int {
long long dTempDist;
int iMinNum;
int i;
//初期値
dTempDist = pdDist[0];
iMinNum = -1;
for (i = 0; i < iClassNum; i++) {
if (dTempDist >= pdDist[i]) {
iMinNum = i;
dTempDist = pdDist[i];
}
}
return iMinNum;
};
int i, j;
int iEndCheckFlag;
while (1) {
for (i = 0; i < M; i++) {
dInitCenterPosit[i] = dCenterPosit[i] = ABs[myrand.randrange(N)];
}
int ok = 1;
for (i = 0; i < M; i++) {
for (j = i + 1; j < M; j++) {
if (dCenterPosit[i] == dCenterPosit[j]) {
ok = 0;
break;
}
}
}
if (ok) {
break;
}
}
while (true) {
//分類パターンの所属クラスタ決定
for (i = 0; i < N; i++) {
//各クラスタとの距離算出
for (j = 0; j < M; j++) {
dTempDistance[j] = dist(dCenterPosit[j], ABs[i]);
}
//最小距離のクラスタ番号取得
iClassNum[i] = fiClassDetermination(M, dTempDistance);
}
//中心位置修正
for (i = 0; i < N; i++) {
assert((iClassNum[i] >= 0) && (iClassNum[i] < M));
iElemNum[iClassNum[i]]++;
dSum[iClassNum[i]][0] += ABs[i].first;
dSum[iClassNum[i]][1] += ABs[i].second;
}
for (i = 0; i < M; i++) {
if (iElemNum[i]) {
dCenterPosit[i].first = dSum[i][0] / (long long)iElemNum[i];
dCenterPosit[i].second = dSum[i][1] / (long long)iElemNum[i];
}
}
//終了チェック 修正前後での各クラスタ距離算出
iEndCheckFlag = 1;
for (i = 0; i < M; i++) {
if ((dCenterPosit[i].first - dInitCenterPosit[i].first) *
(dCenterPosit[i].first - dInitCenterPosit[i].first) +
(dCenterPosit[i].second - dInitCenterPosit[i].second) *
(dCenterPosit[i].second - dInitCenterPosit[i].second) >=
1) {
iEndCheckFlag = 0;
}
}
if (iEndCheckFlag == 1) {
break;
} else {
for (i = 0; i < M; i++) {
dInitCenterPosit[i] = dCenterPosit[i];
}
}
}
return make_pair(iClassNum, dCenterPosit);
}
// TSP with bitDP (loop) O(N^2 2^N)
// 初期値と、dist[v][nv] == -1 の部分などは適宜変更すること
// クラスタのセンターの間のtspを解く
vector<int> bit_dp(vector<pair<long long, long long>>& centers) {
int N = centers.size();
vector<vector<long long>> dp((1 << N), vector<long long>(N, INFll));
for (int i = 1; i < N; i++) {
dp[1 << i][i] = dist(centers[0], centers[i]);
}
for (int bit = 1; bit < (1 << N); bit++) {
for (int v = 0; v < N; v++) {
if (!(bit & (1 << v))) continue;
for (int nv = 0; nv < N; nv++) {
if (bit & (1 << nv)) continue;
chmin(dp[bit | (1 << nv)][nv],
dp[bit][v] + dist(centers[v], centers[nv]));
}
}
}
int tsp_ans = dp[(1 << N) - 1][0];
debug(tsp_ans);
int now = 0;
vector<int> route{now};
int visited_bit = (1 << N) - 1;
long long dist_sum = tsp_ans;
for (int _ = 0; _ < N - 1; _++) {
visited_bit ^= (1 << now);
int last_city = 0;
for (; last_city < N; last_city++) {
if (last_city == now) {
continue;
}
if (dist_sum - dp[visited_bit][last_city] ==
dist(centers[last_city], centers[now])) {
break;
}
}
dist_sum -= dist(centers[last_city], centers[now]);
now = last_city;
route.push_back(now);
}
assert(int(route.size()) == N);
return route;
}
auto solve_cluster(vector<pair<int, int>>& route,
const vector<int>& cities_original_idxs,
const int center_idx,
const vector<pair<long long, long long>>& cities,
const pair<long long, long long>& center) {
assert(cities.size() == cities_original_idxs.size());
int N = cities.size();
assert(N <= 20);
vector<vector<long long>> dp((1 << N), vector<long long>(N + 1, INFll));
dp[0][N] = 0; // 宇宙ステーションが始点
for (int bit = 0; bit < (1 << N); bit++) {
for (int v = 0; v < N; v++) {
chmin(dp[bit][N], dp[bit][v] + alpha * dist(center, cities[v]));
}
// 惑星始点のをやる
for (int v = 0; v < N; v++) {
if (!(bit & (1 << v))) continue;
for (int nv = 0; nv < N; nv++) {
if (bit & (1 << nv)) continue;
// 通常のやつ alpha*alpha*となる
chmin(dp[bit | (1 << nv)][nv],
dp[bit][v] + alpha * alpha * dist(cities[v], cities[nv]));
}
}
// 宇宙ステーション始点のをやる
{
// int v = N;
for (int nv = 0; nv < N; nv++) {
if (bit & (1 << nv)) continue;
// 通常のやつ alpha*となる
chmin(dp[bit | (1 << nv)][nv],
dp[bit][N] + alpha * dist(center, cities[nv]));
}
}
}
int tsp_ans = dp[(1 << N) - 1][N];
assert(tsp_ans != INFll);
debug(tsp_ans);
// 復元
int now = -1;
int visited_bit = (1 << N) - 1;
long long dist_sum = tsp_ans;
// for (int v = 0; v < N; v++) {
// if (dist_sum - dp[visited_bit ^ (1 << v)][v] ==
// alpha * dist(center, cities[v])) {
// now = v;
// }
// }
// if (now == -1) {
for (int v = 0; v < N; v++) {
if (dist_sum - dp[visited_bit][v] == alpha * dist(center, cities[v])) {
now = v;
break;
}
}
// }
assert(now != -1);
dist_sum = dp[visited_bit][now];
route.emplace_back(1, cities_original_idxs[now]);
while (visited_bit) {
debug(visited_bit);
{
int last_city = -1;
for (int v = 0; v < N; v++) {
if (dist_sum - dp[visited_bit ^ (1 << now)][v] ==
alpha * alpha * dist(cities[v], cities[now])) {
last_city = v;
break;
}
}
if (last_city != -1) {
visited_bit ^= (1 << now);
now = last_city;
dist_sum = dp[visited_bit][now];
route.emplace_back(1, cities_original_idxs[now]);
continue;
}
}
{
assert(dist_sum - dp[visited_bit ^ (1 << now)][N] ==
alpha * dist(center, cities[now]));
visited_bit ^= (1 << now);
dist_sum = dp[visited_bit][N];
route.emplace_back(2, center_idx);
for (int v = 0; v < N; v++) {
if (dist_sum - dp[visited_bit][v] ==
alpha * dist(center, cities[v])) {
now = v;
dist_sum = dp[visited_bit][now];
route.emplace_back(1, cities_original_idxs[now]);
break;
}
}
continue;
}
}
assert(dist_sum == 0);
if (route.back() != make_pair(2, center_idx)) {
route.emplace_back(2, center_idx);
}
// assert(int(route.size()) == N);
return;
}
int main() {
int _N, _M;
cin >> _N >> _M;
assert(_N == 100 && _M == 8);
for (int i = 0; i < N; i++) {
int A;
int B;
cin >> A >> B;
ABs[i] = {A, B};
}
debug("----");
vector<int> cluster;
vector<pair<long long, long long>> centers;
while (true) {
auto [_cluster, _centers] = k_means();
cluster = _cluster;
centers = _centers;
bool ok = true;
map<int, int> m;
for (auto& e : cluster) {
m[e]++;
}
for (const auto& [key, value] : m) {
if (value > 16) {
ok = false;
}
}
if (ok) {
break;
}
}
debug(cluster, centers);
vector<pair<int, int>> route;
vector<int> centers_route = bit_dp(centers);
for (int center_idx = 0; center_idx < M; center_idx++) {
pair<long long, long long> center = centers[center_idx];
route.emplace_back(2, centers_route[center_idx] + 1);
vector<int> cities_original_idxs;
vector<pair<long long, long long>> cities;
for (int j = 0; j < N; j++) {
if (cluster[j] == centers_route[center_idx]) {
cities_original_idxs.push_back(j + 1);
cities.push_back(ABs[j]);
}
}
solve_cluster(route, cities_original_idxs,
centers_route[center_idx] + 1, cities, center);
}
int return_idx = 0;
bool ok = false;
for (; return_idx < int(route.size()); return_idx++) {
if (route[return_idx].first == 1 && route[return_idx].second == 1) {
ok = true;
break;
}
}
assert(ok);
assert(return_idx != -1);
rotate(route.begin(), route.begin() + return_idx, route.end());
route.emplace_back(1, 1); // 最初に戻ってくる
for (auto& elem : centers) cout << elem.first << " " << elem.second << '\n';
cout << route.size() << endl;
for (auto& elem : route) cout << elem.first << " " << elem.second << '\n';
return 0;
}