Submission #2012042

---

Source Code Expand

#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>
#include <random>
#include <chrono>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
//#define INFL 9223372036854775807LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}
string YN(bool y) { return (y ? "YES" : "NO"); }
string yn(bool y) { return (y ? "Yes" : "No"); }
string ON(bool y) { return (y ? "OK" : "NG"); }

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;

int dir4[4][2] = { { 0,-1 },{ -1,0 },{ 1,0 },{ 0,1 } };
int dir8[8][2] = { { -1,-1 },{ 0,-1 },{ 1,-1 },{ -1,0 },{ 1,0 },{ -1,1 },{ 0,1 },{ 1,1 } };

// Xoroshiro128+
uint64_t randomSeed[2] = { 10, 20 };
inline static uint64_t rotl(const uint64_t x, int k) {
	return (x << k) | (x >> (64 - k));
}
inline uint64_t randNext(void) {
	const uint64_t s0 = randomSeed[0];
	uint64_t s1 = randomSeed[1];
	const uint64_t result = s0 + s1;

	s1 ^= s0;
	randomSeed[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); // a, b
	randomSeed[1] = rotl(s1, 36); // c

	return result;
}

// [a,b)のほぼ一様乱数
inline int irand(int a, int b) {
	/*
	static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
	uniform_int_distribution<int> dist(a, b - 1);
	return dist(Rand);
	*/
	return (randNext() % (b - a)) + a;
}

double drand(int a, int b) {
	static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
	uniform_real_distribution<double> dist(a, b);
	return dist(Rand);
}

//高速指数関数
#define LOG2   0.693147180559945309417   //log(2)

double exp_fast(double x)
{
	static double waru[7] = { 1.0 / (2 * 3 * 4 * 5 * 6),1.0 / (2 * 3 * 4 * 5),1.0 / (2 * 3 * 4),1.0 / (2 * 3),1.0 / 2,1.0,1.0 };
	static unsigned long long table[16] = {
		0x059B0D3158574ull,  // 2^( 1 /32)-1
		0x11301D0125B51ull,  // 2^( 3 /32)-1
		0x1D4873168B9AAull,  // 2^( 5 /32)-1
		0x29E9DF51FDEE1ull,  // 2^( 7 /32)-1
		0x371A7373AA9CBull,  // 2^( 9 /32)-1
		0x44E086061892Dull,  // 2^( 11 /32)-1
		0x5342B569D4F82ull,  // 2^( 13 /32)-1
		0x6247EB03A5585ull,  // 2^( 15 /32)-1
		0x71F75E8EC5F74ull,  // 2^( 17 /32)-1
		0x82589994CCE13ull,  // 2^( 19 /32)-1
		0x93737B0CDC5E5ull,  // 2^( 21 /32)-1
		0xA5503B23E255Dull,  // 2^( 23 /32)-1
		0xB7F76F2FB5E47ull,  // 2^( 25 /32)-1
		0xCB720DCEF9069ull,  // 2^( 27 /32)-1
		0xDFC97337B9B5Full,  // 2^( 29 /32)-1
		0xF50765B6E4540ull,  // 2^( 31 /32)-1
	};
	double y = 1.0 / (2 * 3 * 4 * 5 * 6 * 7), *p = waru, z, r;
	int q;
	unsigned long long w;
	z = x*(16.0 / LOG2);
	q = (int)z - (x<0);
	r = x - ((q << 1) + 1)*(LOG2 / 32.0);
	w = (unsigned long long)(1023 + (q >> 4)) << 52 ^ table[q & 0xF];
	z = *(double*)&w;
	do {
		y = y*r + (*p);
		p++;
	} while (p < waru + 7);
	return y*z;
}
#undef LOG2
//=======ここまでテンプレート===============================================

#define DEBUG false
/*
#include"toolkit\graph\fullgraph.h"
#include"toolkit\graph\kingsgraph_square.h"
#include"toolkit\graph\randomgraph.h"
//*/
vi weight, conw;
Graph G;
int V, E, Vemb, Eemb, SIZE;

int idx(Pi p) {
	return p.first * SIZE + p.second + 1;
}

class State {
	int _score;
public:
	vPi match;
	int swapa, swapb;

	State(int v) :_score(-1), match(vPi(V)) {}
	bool operator<(State s) { return _score < s.score(); }
	bool operator>(State s) { return _score > s.score(); }

	int score() {
		if (_score >= 0)return _score;
		_score = 0;
		rep(i, V) {
			for (auto e : G[i]) {
				if (abs(match[e.from].first - match[e.to].first) <= 1 && abs(match[e.from].second - match[e.to].second) <= 1) {
					_score += e.cost;
				}
			}
		}
		return _score /= 2;
	}
	void reset_score() { _score = -1; }
	void Swap(int a, int b) {
		// スコア取り消し
		for (auto e : G[a]) {
			if (abs(match[e.from].first - match[e.to].first) <= 1 && abs(match[e.from].second - match[e.to].second) <= 1) {
				_score -= e.cost;
			}
		}
		for (auto e : G[b]) {
			if (abs(match[e.from].first - match[e.to].first) <= 1 && abs(match[e.from].second - match[e.to].second) <= 1) {
				_score -= e.cost;
			}
		}
		// スワップ
		swap(match[a], match[b]);
		// スコア加算
		for (auto e : G[a]) {
			if (abs(match[e.from].first - match[e.to].first) <= 1 && abs(match[e.from].second - match[e.to].second) <= 1) {
				_score += e.cost;
			}
		}
		for (auto e : G[b]) {
			if (abs(match[e.from].first - match[e.to].first) <= 1 && abs(match[e.from].second - match[e.to].second) <= 1) {
				_score += e.cost;
			}
		}
	}
	void randomSwap() {
		swapa = irand(0, V);
		swapb = irand(0, V);
		Swap(swapa, swapb);
	}
	/*
	void randomNearSwap() {
		swapa = irand(0, V);
		int d = irand(0, 4);
		Pi pb;
		do {
			pb = mp(match[swapa].first + dir4[d][0], match[swapa].second + dir4[d][1]);
			d = irand(0, 4);
		} while (dict.find(idx(pb)) == dict.end());
		swapb = dict[idx(pb)];
		Swap(swapa, swapb);
	}
	*/
	void redo() {
		Swap(swapa, swapb);
	}

	void debug_show() {
		cout << "debug_show(): " << endl;
		cout << "score: " << score() << endl;
		rep(i, V) {
			cout << i + 1 << " " << idx(match[i]) << endl;
		}
	}
	void ans_show() {
		rep(i, V) {
			cout << i + 1 << " " << idx(match[i]) << endl;
		}
	}
};

State next(State st) {
	State newState = st;
	newState.reset_score();
	newState.randomSwap();
	return newState;
}
/*
State nearNext(State st) {
	State newState = st;
	newState.reset_score();
	newState.randomNearSwap();
	return newState;
}
*/
int main(void) {
	// 乱数シード作成
	static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));
	uniform_int_distribution<uint64_t> dist(1, ULLONG_MAX);
	randomSeed[0] = dist(Rand);
	randomSeed[1] = dist(Rand);

	chrono::system_clock::time_point start = chrono::system_clock::now();
	scanf("%d %d", &V, &E);
	G = Graph(V);
	weight = vi(V);
	conw = vi(V);
	rep(i, E) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		u--; v--;
		G[u].push_back(Edge{ u,v,w });
		G[v].push_back(Edge{ v,u,w });
		weight[u] += w * 2;
		weight[v] += w * 2;
	}
	rep(i, V) {
		for (auto e : G[i]) {
			conw[i] += weight[e.to];
		}
		conw[i] += weight[i] * 1;
	}
	rep(i, V) {
		weight[i] += conw[i];
	}

	vPi nodes(V);
	rep(i, V) {
		nodes[i] = mp(weight[i], i);
	}
	sort(rall(nodes));

	scanf("%d %d", &Vemb, &Eemb);
	rep(i, Eemb) {
		int u, v;
		scanf("%d %d", &u, &v);
	}
	SIZE = (int)(sqrt(Vemb) + 0.5);

	int a = (int)sqrt(V);
	int b = a;
	if (a*(b + 1) <= V)b++;
	if (DEBUG)cout << "a,b = " << a << "," << b << endl;
	Pi center = mp(0, 0);
	vPi dir = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
	if (a == b) {
		center = mp(a / 2, a / 2);
		if (a % 2 == 0) {
			dir = { { -1,0 },{ 0,-1 },{ 1,0 },{ 0,1 } };
		}
		else {
			dir = { { 1,0 },{ 0,1 },{ -1,0 },{ 0,-1 } };
		}
	}
	else {
		center = mp(a / 2, b / 2);
		if (b % 2 == 0) {
			dir = { { 0,-1 },{ 1,0 },{ 0,1 },{ -1,0 } };
		}
		else {
			dir = { { 0,1 },{ -1,0 },{ 0,-1 },{ 1,0 } };
		}
	}

	Pi pos = center;
	int cnt = 0, step = 1, d = 0;
	State st(V);
	while (true) {
		try {
			rep(k, 2) {
				rep(i, step) {
					if (DEBUG) {
						cout << "======" << endl;
						cout << "pos: " << debug_show(pos) << endl;
						cout << "dir[" << d << "]: " << debug_show(dir[d]) << endl;
					}
					st.match[nodes[cnt].second] = pos;
					//st.dict[idx(pos)] = nodes[cnt].second;
					pos.first += dir[d].first;
					pos.second += dir[d].second;
					cnt++;
					if (cnt == V) {
						//goto finish;
					}
				}
				d = (d + 1) % 4;
				if (pos == mp(a, 0)) {
					break;
				}
			}
			if (pos == mp(a, 0)) {
				break;
			}
			step++;
		}
		catch (char *e) {
			cout << e << endl;
			return 0;
		}
	}
	int res = V - a*b;
	if (res == b - 1) {
		rep(i, res) {
			st.match[nodes[cnt].second] = pos;
			//st.dict[idx(pos)] = nodes[cnt].second;
			pos.second++;
			cnt++;
		}
	}
	else {
		pos = mp(a, 1);
		rep(i, res) {
			st.match[nodes[cnt].second] = pos;
			//st.dict[idx(pos)] = nodes[cnt].second;
			pos.second++;
			cnt++;
		}
	}

finish:

	State bestState = st;
	int bestScore = st.score();
	int currentScore = bestScore;

	const ll T = 9900;	// 終了時間
	const int R = 1000000;	// 適当な値
	const double startTemp = 100;	// 初期温度
	const double endTemp = 30;	// 終了温度

	// 経過時間を記録
	ll t = chrono::duration_cast<std::chrono::milliseconds>(chrono::system_clock::now() - start).count();

	int iteration = 0;

	while (t < T) {
		//iteration++;
		rep(i, 10000) {
			st.randomSwap();

			// 次の状態へ移行
			int nextScore = st.score();
			
			// 現在の温度（最初はstartTemp, 最後はendTemp）
			double temp = startTemp + (endTemp - startTemp)*t / T;
			// 焼きなましによる遷移確率（スコアが改善すれば必ず遷移）
			double probability = exp_fast((nextScore - currentScore) / temp);
			// 遷移するか否か
			bool FORCE_NEXT = probability * R >(double)(randNext() % R);
			
			if (FORCE_NEXT /*nextScore > currentScore*/) {
				// 遷移を確定させる
				currentScore = nextScore;
				
				if (currentScore > bestScore) {
					// 最良の状態とスコアを記録
					bestScore = currentScore;
					bestState = st;
				}
				
			}
			else {
				// 前の状態に戻る
				st.redo();
			}
		}
		// 経過時間を更新
		t = chrono::duration_cast<std::chrono::milliseconds>(chrono::system_clock::now() - start).count();
	}

	if (DEBUG) cout << "itteration: " << iteration << endl;
	if (DEBUG) bestState.debug_show();

	bestState.ans_show();
	//st.ans_show();

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:271:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &V, &E);
                        ^
./Main.cpp:277:32: 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:300:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &Vemb, &Eemb);
                              ^
./Main.cpp:303:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^

Judge Result