Submission #1872840

---

Source Code Expand

#include <vector>
#include <cfloat>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <random>
#include <queue>
#include <list>
#include <map>
#include <array>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
 
vector<int>connect[600];
vector<pair<int,int> >node[600];
vector<pair<int,int> >edgeList;
 
int dummy_score;
int ans[600];
int memo[65][65];
int SZ;
 
int V;
int E;
int edge[600][600];
int vertex[30000][2];
 
int V_emb;
int E_emb;
int emb_edge[3605][3605];

int calc_score_sub(int left);
int calc_score();
void SA();
ll make_rand();
void gen_rand_next_state(int iter);
double gen_per_rand(const ll res = 1LL << 60) {
	return 1.0 * (make_rand() % res) / (res - 1);
}
double probability(double e1, double e2, double t) {
	if (e1 <= e2) {
		return 1;
	}
	else {
		double res = exp((-e1 + e2) / t);
		return res;
	}
}
 
chrono::system_clock::time_point start;
 
int main(){

	start = chrono::system_clock::now();
 
	scanf("%d %d",&V,&E);
 
	int u,v,w;
 
	int i;
 
	for(i=0;i<E;i++){
	scanf("%d %d %d",&u,&v,&w);
	edge[u][v]=w;
	edge[v][u]=w;
	vertex[i][0]=u;
	vertex[i][1]=v;
	connect[u].push_back(v);
	connect[v].push_back(u);
	node[u].push_back(make_pair(w,v));
	node[v].push_back(make_pair(w,u));
	}
 
	scanf("%d %d",&V_emb,&E_emb);
 
	for(i=0;i<E_emb;i++){
	scanf("%d %d",&u,&v);
	emb_edge[u][v]=1;
	emb_edge[v][u]=1;
	}
 
 
	for(i=2;i<=100;i++){
		if(i*i==V_emb){
			SZ=i;
			break;
		}
	}
 
	int N=(int) sqrt(V_emb) + 2;
	int n=(int) ceil(sqrt(V));
 
	int offset=(N-n)/2;
	int y=offset;
	int x=offset;
 
	for(i=1;i<=V;i++){
	int z=(y*N)+x;
	ans[i]=z;
	x++;
	if (x == n + offset) {
		x = offset;
		y++;
	}
	}
 
	for (i = 1; i <= V; i++) {
	int z = ans[i];
	y = z / N - 1;
	x = z % N - 1;
	int zz=y * (N - 2) + x + 1;
	ans[i]= zz;
	memo[(zz-1)/SZ][(zz-1)%SZ]=i;
	}
 
	for(i=1;i<=V;i++){
		sort(node[i].begin(),node[i].end());
		reverse(node[i].begin(),node[i].end());
		int limit = max(12, (int) (node[i].size() * 0.15));
 
		for(int k=0;k<limit;k++){
 
		if(k>=node[i].size()){break;}
 
		for (int j = 0; j < node[i][k].first; j++) {
			edgeList.push_back(make_pair(i,node[i][k].second));
			edgeList.push_back(make_pair(node[i][k].second,i));
		}
		}
	}
	random_shuffle(edgeList.begin(),edgeList.end());

	SA();
 
return 0;
}
int calc_score(){
 
	int score=0;
 
	int i;
 
	for(i=0;i<E;i++){
		if(emb_edge[ans[vertex[i][0]]][ans[vertex[i][1]]]==1){
			score+=edge[vertex[i][0]][vertex[i][1]];
		}
	}
	return score;
}
int calc_score_sub(int left){
 
	int score=0;
	int x=(ans[left]-1)%SZ;
	int y=(ans[left]-1)/SZ;
 
	int dx[8]={-1,0,1,-1,1,-1,0,1};
	int dy[8]={-1,-1,-1,0,0,1,1,1};
 
	int i;
 
	for(i=0;i<8;i++){
		if(0<=y+dy[i]&&y+dy[i]<SZ&&0<=x+dx[i]&&x+dx[i]<SZ){
			score+=edge[left][memo[y+dy[i]][x+dx[i]]];
		}
	}
	return score;
 
}
void gen_rand_next_state(int iter) {
 
	int i,j;
 
	int diff_score;
	int t=ans[edgeList[iter].first];
	int end_point=edgeList[iter].second;
 
	int dx[8]={-1,0,1,-1,1,-1,0,1};
	int dy[8]={-1,-1,-1,0,0,1,1,1};
	int dd[8]={-SZ-1,-SZ,-SZ+1,-1,1,SZ-1,SZ,SZ+1};
 
	int x=(ans[end_point]-1)%SZ;
	int y=(ans[end_point]-1)/SZ;
	int r;
	while(1){
		r=make_rand()%8;
		if(0<=x+dx[r]&&x+dx[r]<SZ&&0<=y+dy[r]&&y+dy[r]<SZ){
			if(t!=ans[end_point]+dd[r]){
			break;
			}
		}
	}
 
	if(memo[y+dy[r]][x+dx[r]]>0){
	
		int a=edgeList[iter].first;
		int b=memo[y+dy[r]][x+dx[r]];

		diff_score=calc_score_sub(a)+calc_score_sub(b);

		swap(memo[(t-1)/SZ][(t-1)%SZ],memo[y+dy[r]][x+dx[r]]);
		swap(ans[a],ans[b]);

		diff_score-=calc_score_sub(a)+calc_score_sub(b);
 
	}
	else{
		int a=edgeList[iter].first;
		int b=((y+dy[r])*SZ)+(x+dx[r])+1;

		diff_score=calc_score_sub(a);

		int t2=memo[(t-1)/SZ][(t-1)%SZ];
		memo[(t-1)/SZ][(t-1)%SZ]=0;
		memo[y+dy[r]][x+dx[r]]=t2;
		ans[a]=b;

		diff_score-=calc_score_sub(a);

	}

	dummy_score-=diff_score;
 
}
ll make_rand() {
	static ll x = 123456789;
	static ll y = 362436069;
	static ll z = 521288629;
	static ll w = 88675123;
	ll t;
	t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
void SA(){
 
	int c_field[600];
	memcpy(c_field, ans, sizeof(ans));
	int c_score = calc_score();
 
	dummy_score=c_score;
 
	int b_field[600];
	memcpy(b_field, c_field, sizeof(c_field));
	int b_score = c_score;
 
	double param1, param2;
 
	double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
 
	double simulate_time = (9.99 - diff)*1000.0;
 
	param1 = 1.0 / (simulate_time / 2.2);
	param2 = 1.0 / exp(2.2);
 
	int n_field[600];
	int n_memo[65][65];
 
	int iter=0;
 
	while (1) {
 
		//if (iter % 1000 == 0) {
		//	cout << iter << " " << c_score << endl;
		//}
 
		// 時間になったので打ち切り
		diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
		if (diff > 9.99) {
			break;
		}
 
		memcpy(n_field,ans,sizeof(ans));
		memcpy(n_memo,memo,sizeof(memo));
		int temp_score=dummy_score;
 
		gen_rand_next_state(iter%edgeList.size());
		int n_score = dummy_score;
 
		// 最高の値を更新
		if (n_score > b_score) {
			memcpy(b_field, ans, sizeof(ans));
			b_score = n_score;
		}
		// 状態遷移するか判定
 
		if (gen_per_rand() <= probability(c_score, n_score, 5.0 * exp((9.99 - diff) * param1*1000.0) * param2)) {
			c_score = n_score;
		}
		else{
			memcpy(ans,n_field,sizeof(n_field));
			memcpy(memo,n_memo,sizeof(n_memo));
			dummy_score=temp_score;
		}
		iter++;
	}
 
	//cout << "best_score : " << b_score << endl;
 
	int i;

	for (i = 1; i <= V; i++) {
		printf("%d %d\n",i,b_field[i]);
	}
 
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&V,&E);
                      ^
./Main.cpp:73:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&u,&v,&w);
                            ^
./Main.cpp:84:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&V_emb,&E_emb);
                              ^
./Main.cpp:87:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&u,&v);
                      ^

Judge Result