結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー rinrion
提出日時 2022-08-05 17:44:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 4,971 bytes
コンパイル時間 2,013 ms
実行使用メモリ 4,688 KB
スコア 6,054,397
最終ジャッジ日時 2022-08-05 17:44:52
合計ジャッジ時間 33,577 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include<chrono> 
using namespace std;

long double ENG(int x1,int y1, int x2, int y2,int t){
	long double uq= sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	return uq*uq*t;
}

long SCORE(long long s){
	return (long)(1000000000/(1000+(long)sqrt(s)));
}

struct unionfind{
	//par=親 siz=グループの頂点数
	vector<int>par,siz;

	unionfind(int n):par(n,-1),siz(n,1){}

	//根を求める
	int root(int x){
		if(par[x]==-1)return x;
		else return par[x]=root(par[x]);
	}

	//xとyが同グループか(根が同じか)
	bool issame(int x,int y){
		return root(x)==root(y);
	}

	//xを含むグループとyを含むグループを併合する
	bool unite(int x,int y){
		x=root(x),y=root(y);
		if(x==y)return false;
		//y側のサイズが小さくなるようにする
		if(siz[x]<siz[y])swap(x,y);

		//yをxの子とする
		par[y]=x;
		siz[x]+=siz[y];
		return true;
	}

	int size(int x){
		return siz[root(x)];
	}
};

static uint32_t randxor(){//ランダム数(int)
	static uint32_t x = 123456789;
	static uint32_t y = 362436069;
	static uint32_t z = 521288629;
	static uint32_t w = 88675123;
	uint32_t t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

static double rand01(){//ランダム数(0.0以上1.0未満の小数)
	return(randxor()+0.5)*(1.0/UINT_MAX);
}

double time_limit=950;
double gettime;
chrono::system_clock::time_point  time_now;
chrono::system_clock::time_point  time_start = chrono::system_clock::now(); 

double start_temp=500, end_temp=0.001,temp;

int main(){

	int n,m;
	cin>>n>>m;
	
	vector<int>a(n),b(n);
	for(int i=0; i<n; i++){
		cin>>a[i]>>b[i];
	}

//	vector<pair<double,int>>eng_all;
	vector<vector<pair<long double,int>>>eng(100,vector<pair<long double,int>>(100));
	vector<vector<pair<long double,int>>>eng_sr(100,vector<pair<long double,int>>(100));

	for(int i=0;i<100;i++){
		for(int j=0;j<100;j++){
			if(i!=j){
//				eng_all.emplace_back(eu2(a[i],b[i],a[j],b[j]),j);
				eng[i][j]=make_pair(ENG(a[i],b[i],a[j],b[j],25),j);
				eng_sr[i][j]=eng[i][j];
			}
			else{
				eng[i][j]=make_pair(1000000000001,-1);
				eng_sr[i][j]=eng[i][j];
			}
		}
		sort(eng_sr[i].begin(),eng_sr[i].end());
	}

	vector<pair<int,int>>cd(8);//ロボてりーの位置　×8
	for(int i=0; i<8; i++){
		cd[i].first=0;
		cd[i].second=0;
	}

	vector<pair<int,int>>tr,tr_best;
	bitset<100>visited;
	int now=0;
	visited[now]=true;
	tr.emplace_back(1,0);

	while(true){
		bool jdg=false;
		for(int i=0; i<99; i++){
			if(!(visited[eng_sr[now][i].second])){
				int next=eng_sr[now][i].second;
				tr.emplace_back(1,next);
				now=next;
				visited[next]=true;
				jdg=true;
				break;
			}
		}
		if(!jdg)break;
	}
	tr.emplace_back(1,0);

	long double eng_sum=0;
	for(int i=0; i<100; i++){
		eng_sum+=(long double)eng[tr[i].second][tr[i+1].second].first;
	}

	long score,score_best;
	score=SCORE(eng_sum);
	score_best=score;
	tr_best=tr;

	long double cnt=0,cnt_p1=0,cnt_p2=0,cnt_rec;

	while(gettime<time_limit){
		if((int)cnt%5000==0){
			time_now = chrono::system_clock::now(); 
			gettime = chrono::duration_cast<chrono::milliseconds>(time_now-time_start).count();
			temp=start_temp+(end_temp-start_temp)*gettime/time_limit;
		}

		int A=randxor()%99+1, B=randxor()%99+1;

		int na=tr[A-1].second,a=tr[A].second,an=tr[A+1].second;
		int nb=tr[B-1].second,b=tr[B].second,bn=tr[B+1].second;

		int eng_m=(int)(eng[na][a].first+eng[a][an].first+eng[nb][b].first+eng[b][bn].first);
		int eng_p=(int)(eng[na][b].first+eng[b][an].first+eng[nb][a].first+eng[a][bn].first);

		int score_r=SCORE(eng_sum-eng_m+eng_p);

		double prob=exp((score_r-score)/temp);
		double rnd_d=rand01();

		bool judge=false;
		if(prob>rnd_d){
			tr[A].second=b,tr[B].second=a;
			eng_sum=eng_sum-eng_m+eng_p;
			score=score_r;
			if(score>score_best){
				tr_best=tr;
				score_best=score;
			}

		if(gettime<475)cnt_p1++;
		else cnt_p2++;
		}
		
		cnt++;
	}

	for(auto x:cd){
		cout<<x.first<<" "<<x.second<<endl;
	}
	cout<<tr_best.size()<<endl;
	for(auto x:tr_best){
		cout<<x.first<<" "<<x.second+1<<endl;
	}

// cout<<"score "<<score_best<<" cnt "<<cnt<<" "<<fixed<<setprecision(6)<<(cnt_p1+cnt_p2)/cnt<<endl;

}

/*	
	sort(eng_all.begin(),eng_all.end());
	
	vector<vector<int>>g(100,vector<int>());
	
	unionfind uf(n);

	for(int i=0; i<eng_all.size(); i++){
		int W=get<0>(eng_all[i]),U=get<1>(eng_all[i]),V=get<2>(eng_all[i]);
		if(!uf.issame(U,V)){
			uf.unite(U,V);
			g[U].push_back(V);
			g[V].push_back(U);
		}
	}
*/

/*
◇要素数の多い配列は　pairを使う 呼び出し:get<0>(変数名)
◇vector<bool>は　bitsetを使う bitの並びでtrue/falseを設定できる
	宣言 bitset<5> 変数名;
	変更 bit[0]=true;
	出力 cout<< bit[0]<<endl;
◇vector<pair<x,x>>に要素を追加するときは emplace_back	 	を使う
	pairの要素を追加  変数名.emplace_back(1,2);  make_pairは不要
◇set<pair<x,x>> なら emplace を使う
	pairの要素を追加  変数名.emplace(1,2);
*/
0