#783121 (C++14) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	square1001
提出日時	2022-07-30 16:31:37
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	984 ms / 1,000 ms
コード長	7,548 bytes
コンパイル時間	863 ms
実行使用メモリ	3,828 KB
スコア	8,399,835
最終ジャッジ日時	2022-07-30 16:32:21
合計ジャッジ時間	32,245 ms
ジャッジサーバーID （参考情報）	judge12 / judge10
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	955 ms 3,672 KB
testcase_01	AC	956 ms 3,660 KB
testcase_02	AC	955 ms 3,588 KB
testcase_03	AC	957 ms 3,660 KB
testcase_04	AC	955 ms 3,680 KB
testcase_05	AC	956 ms 3,688 KB
testcase_06	AC	956 ms 3,708 KB
testcase_07	AC	955 ms 3,584 KB
testcase_08	AC	956 ms 3,592 KB
testcase_09	AC	955 ms 3,656 KB
testcase_10	AC	955 ms 3,580 KB
testcase_11	AC	955 ms 3,580 KB
testcase_12	AC	956 ms 3,684 KB
testcase_13	AC	955 ms 3,744 KB
testcase_14	AC	955 ms 3,672 KB
testcase_15	AC	956 ms 3,824 KB
testcase_16	AC	957 ms 3,744 KB
testcase_17	AC	956 ms 3,584 KB
testcase_18	AC	956 ms 3,588 KB
testcase_19	AC	955 ms 3,668 KB
testcase_20	AC	977 ms 3,592 KB
testcase_21	AC	955 ms 3,708 KB
testcase_22	AC	976 ms 3,628 KB
testcase_23	AC	955 ms 3,684 KB
testcase_24	AC	977 ms 3,664 KB
testcase_25	AC	954 ms 3,628 KB
testcase_26	AC	962 ms 3,588 KB
testcase_27	AC	955 ms 3,828 KB
testcase_28	AC	956 ms 3,628 KB
testcase_29	AC	984 ms 3,668 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cmath>
#include <ctime>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;

namespace myrandom {
	uint64_t seed = 123456789ULL;
	uint64_t xorshift64() {
		seed ^= seed << 13;
		seed ^= seed >> 7;
		seed ^= seed << 17;
		return seed;
	}
	int next_int(int l, int r) {
		return l + int(xorshift64() % (r - l));
	}
	double next_double(double l, double r) {
		return l + double(xorshift64()) / double(uint64_t(-1)) * (r - l);
	}
}

class point2d {
public:
	int x, y;
	point2d() : x(0), y(0) {};
	point2d(int x_, int y_) : x(x_), y(y_) {};
	point2d& operator+=(const point2d& p) {
		x += p.x;
		y += p.y;
		return (*this);
	}
	point2d& operator-=(const point2d& p) {
		x -= p.x;
		y -= p.y;
		return (*this);
	}
	point2d operator+(const point2d& p) const {
		return point2d(*this) += p;
	}
	point2d operator-(const point2d& p) const {
		return point2d(*this) -= p;
	}
	int norm() const {
		return x * x + y * y;
	}
};

class answer_container {
public:
	vector<point2d> stations;
	vector<pair<int, int> > path;
	answer_container() : stations(vector<point2d>()), path(vector<pair<int, int> >()) {};
	answer_container(const std::vector<point2d>& stations_, const std::vector<pair<int, int> >& path_) : stations(stations_), path(path_) {};
};

class quadratic {
public:
	// ax^2 + bx + c
	int a, b, c;
	quadratic() : a(0), b(0), c(0) {};
	quadratic(int a_, int b_, int c_) : a(a_), b(b_), c(c_) {};
	quadratic& operator+=(const quadratic& q) {
		a += q.a;
		b += q.b;
		c += q.c;
		return (*this);
	}
	quadratic& operator-=(const quadratic& q) {
		a -= q.a;
		b -= q.b;
		c -= q.c;
		return (*this);
	}
	quadratic operator+(const quadratic& q) const {
		return quadratic(*this) += q;
	}
	quadratic operator-(const quadratic& q) const {
		return quadratic(*this) -= q;
	}
	int extreme_point() const {
		if (a == 0) {
			assert(b == 0);
			return 0;
		}
		auto divide_and_round = [](int x, int y) {
			if (y > 0) {
				x = x * 2 + y;
				y *= 2;
			}
			else {
				x = x * -2 - y;
				y *= -2;
			}
			return (x >= 0 ? x / y : -((-x + y - 1) / y));
		};
		return divide_and_round(-b, 2 * a);
	}
	int extreme_value() const {
		int x = extreme_point();
		return a * x * x + b * x + c;
	}
};

answer_container solve(int N, int M, const std::vector<point2d>& P, const double TLE) {
	vector<int> perm(2 * N + 1);
	for (int i = 0; i <= N; i++) {
		perm[2 * i] = i % N;
		if (i % N != 0) {
			swap(perm[2 * i], perm[myrandom::next_int(1, i + 1) * 2]);
		}
	}
	for (int i = 0; i < N; i++) {
		perm[2 * i + 1] = myrandom::next_int(-1, M);
	}
	vector<quadratic> qbasex(N);
	vector<quadratic> qbasey(N);
	for (int i = 0; i < N; i++) {
		qbasex[i] = quadratic(1, -2 * P[i].x, P[i].x * P[i].x);
		qbasey[i] = quadratic(1, -2 * P[i].y, P[i].y * P[i].y);
	}
	vector<quadratic> qx(M, quadratic(0, 0, 0));
	vector<quadratic> qy(M, quadratic(0, 0, 0));
	for (int i = 0; i < N; i++) {
		if (perm[2 * i + 1] != -1) {
			int id = perm[2 * i + 1];
			qx[id] += qbasex[perm[2 * i]] + qbasex[perm[2 * i + 2]];
			qy[id] += qbasey[perm[2 * i]] + qbasey[perm[2 * i + 2]];
		}
	}
	int cost1 = 0, cost2 = 0;
	for (int i = 0; i < N; i++) {
		if (perm[2 * i + 1] == -1) {
			cost1 += (P[perm[2 * i]] - P[perm[2 * i + 2]]).norm();
		}
	}
	for (int i = 0; i < M; i++) {
		cost2 += qx[i].extreme_value();
		cost2 += qy[i].extreme_value();
	}
	int initial_t = clock();
	int iteration = 0;
	while (double(clock() - initial_t) / CLOCKS_PER_SEC < TLE) {
		iteration += 1;
		int tp = myrandom::next_int(0, 2);
		int vl = -1, vr = -1, next_idl = -1, next_idr = -1;
		vector<quadratic> sqx = qx;
		vector<quadratic> sqy = qy;
		int next_cost1 = cost1;
		if (tp == 0) {
			// change of one edge
			vl = myrandom::next_int(0, N);
			int id = perm[2 * vl + 1];
			int va = perm[2 * vl];
			int vb = perm[2 * vl + 2];
			next_idl = ((id + 1) + myrandom::next_int(1, M + 1)) % (M + 1) - 1;
			if (id != -1) {
				sqx[id] -= (qbasex[va] + qbasex[vb]);
				sqy[id] -= (qbasey[va] + qbasey[vb]);
			}
			else {
				next_cost1 -= (P[va] - P[vb]).norm();
			}
			if (next_idl != -1) {
				sqx[next_idl] += (qbasex[va] + qbasex[vb]);
				sqy[next_idl] += (qbasey[va] + qbasey[vb]);
			}
			else {
				next_cost1 += (P[va] - P[vb]).norm();
			}
		}
		else {
			do {
				vl = myrandom::next_int(1, N + 1);
				vr = myrandom::next_int(1, N + 1);
			} while(vr - vl <= 1);
			next_idl = myrandom::next_int(-1, M);
			next_idr = myrandom::next_int(-1, M);
			// suppose reverse(perm.begin() + (2 * vl), perm.begin() + (2 * vr - 1))
			// (vl-1)-vl, (vr-1)-vr --> (vl-1)-(vr-1), vl-vr
			int idl = perm[2 * vl - 1];
			int idr = perm[2 * vr - 1];
			int va = perm[2 * vl - 2];
			int vb = perm[2 * vl];
			int vc = perm[2 * vr - 2];
			int vd = perm[2 * vr];
			if (idl != -1) {
				sqx[idl] -= (qbasex[va] + qbasex[vb]);
				sqy[idl] -= (qbasey[va] + qbasey[vb]);
			}
			else {
				next_cost1 -= (P[va] - P[vb]).norm();
			}
			if (idr != -1) {
				sqx[idr] -= (qbasex[vc] + qbasex[vd]);
				sqy[idr] -= (qbasey[vc] + qbasey[vd]);
			}
			else {
				next_cost1 -= (P[vc] - P[vd]).norm();
			}
			if (next_idl != -1) {
				sqx[next_idl] += (qbasex[va] + qbasex[vc]);
				sqy[next_idl] += (qbasey[va] + qbasey[vc]);
			}
			else {
				next_cost1 += (P[va] - P[vc]).norm();
			}
			if (next_idr != -1) {
				sqx[next_idr] += (qbasex[vb] + qbasex[vd]);
				sqy[next_idr] += (qbasey[vb] + qbasey[vd]);
			}
			else {
				next_cost1 += (P[vb] - P[vd]).norm();
			}
		}
		int next_cost2 = 0;
		for (int i = 0; i < M; i++) {
			next_cost2 += sqx[i].extreme_value();
			next_cost2 += sqy[i].extreme_value();
		}
		int cost = cost1 * 25 + cost2 * 5;
		int next_cost = next_cost1 * 25 + next_cost2 * 5;
		if (cost >= next_cost) {
			qx = sqx;
			qy = sqy;
			cost1 = next_cost1;
			cost2 = next_cost2;
			if (tp == 0) {
				perm[2 * vl + 1] = next_idl;
			}
			else {
				reverse(perm.begin() + (2 * vl), perm.begin() + (2 * vr - 1));
				perm[2 * vl - 1] = next_idl;
				perm[2 * vr - 1] = next_idr;
			}
		}
	}
	vector<point2d> stations(M);
	for (int i = 0; i < M; i++) {
		stations[i].x = qx[i].extreme_point();
		stations[i].y = qy[i].extreme_point();
	}
	vector<pair<int, int> > path;
	for (int i = 0; i <= 2 * N; i++) {
		if (i % 2 == 0) {
			path.push_back(make_pair(1, perm[i]));
		}
		else if (perm[i] != -1) {
			path.push_back(make_pair(2, perm[i]));
		}
	}
	cerr << "Loops = " << iteration << endl;
	return answer_container(stations, path);
}

int calculate_cost(int N, int M, const vector<point2d>& P, const answer_container& answer) {
	int cost = 0;
	for (int i = 0; i < int(answer.path.size()) - 1; i++) {
		pair<int, int> u1 = answer.path[i];
		pair<int, int> u2 = answer.path[i + 1];
		point2d p1 = (u1.first == 1 ? P[u1.second] : answer.stations[u1.second]);
		point2d p2 = (u2.first == 1 ? P[u2.second] : answer.stations[u2.second]);
		cost += (p1 - p2).norm() * (u1.first == 1 ? 5 : 1) * (u2.first == 1 ? 5 : 1);
	}
	return cost;
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<point2d> P(N);
	for (int i = 0; i < N; i++) {
		cin >> P[i].x >> P[i].y;
	}
	answer_container answer = solve(N, M, P, 0.95);
	for (int i = 0; i < M; i++) {
		cout << answer.stations[i].x << ' ' << answer.stations[i].y << endl;
	}
	cout << answer.path.size() << endl;
	for (int i = 0; i < int(answer.path.size()); i++) {
		cout << answer.path[i].first << ' ' << answer.path[i].second + 1 << endl;
	}
	int cost = calculate_cost(N, M, P, answer);
	cerr << "Final Cost = " << cost << endl;
	cerr << "Final Score = " << 1.0e+9 / (1.0e+3 + sqrt(cost)) << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード