結果

問題 No.5016 Worst Mayor
ユーザー square1001square1001
提出日時 2023-04-29 16:53:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,294 ms / 2,000 ms
コード長 7,183 bytes
コンパイル時間 2,081 ms
コンパイル使用メモリ 101,344 KB
実行使用メモリ 24,276 KB
スコア 24,258,969,951
平均クエリ数 400.00
最終ジャッジ日時 2023-04-29 16:56:16
合計ジャッジ時間 69,355 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,258 ms
23,616 KB
testcase_01 AC 1,264 ms
23,892 KB
testcase_02 AC 1,289 ms
24,276 KB
testcase_03 AC 1,263 ms
23,712 KB
testcase_04 AC 1,245 ms
24,012 KB
testcase_05 AC 1,239 ms
24,228 KB
testcase_06 AC 1,283 ms
23,376 KB
testcase_07 AC 1,273 ms
23,244 KB
testcase_08 AC 1,255 ms
24,264 KB
testcase_09 AC 1,253 ms
23,820 KB
testcase_10 AC 1,290 ms
23,892 KB
testcase_11 AC 1,293 ms
24,132 KB
testcase_12 AC 1,294 ms
23,520 KB
testcase_13 AC 1,268 ms
24,240 KB
testcase_14 AC 1,259 ms
23,364 KB
testcase_15 AC 1,248 ms
23,412 KB
testcase_16 AC 1,274 ms
23,352 KB
testcase_17 AC 1,241 ms
23,412 KB
testcase_18 AC 1,233 ms
24,012 KB
testcase_19 AC 1,232 ms
23,400 KB
testcase_20 AC 1,217 ms
23,520 KB
testcase_21 AC 1,239 ms
23,292 KB
testcase_22 AC 1,217 ms
23,892 KB
testcase_23 AC 1,232 ms
24,132 KB
testcase_24 AC 1,255 ms
23,496 KB
testcase_25 AC 1,234 ms
23,400 KB
testcase_26 AC 1,236 ms
23,916 KB
testcase_27 AC 1,230 ms
24,036 KB
testcase_28 AC 1,225 ms
23,280 KB
testcase_29 AC 1,226 ms
24,132 KB
testcase_30 AC 1,215 ms
23,232 KB
testcase_31 AC 1,239 ms
23,292 KB
testcase_32 AC 1,241 ms
23,364 KB
testcase_33 AC 1,234 ms
23,916 KB
testcase_34 AC 1,245 ms
23,388 KB
testcase_35 AC 1,243 ms
24,036 KB
testcase_36 AC 1,228 ms
23,916 KB
testcase_37 AC 1,237 ms
24,024 KB
testcase_38 AC 1,245 ms
24,216 KB
testcase_39 AC 1,231 ms
23,808 KB
testcase_40 AC 1,242 ms
23,916 KB
testcase_41 AC 1,226 ms
24,036 KB
testcase_42 AC 1,239 ms
24,228 KB
testcase_43 AC 1,236 ms
24,024 KB
testcase_44 AC 1,244 ms
23,700 KB
testcase_45 AC 1,236 ms
23,244 KB
testcase_46 AC 1,275 ms
23,244 KB
testcase_47 AC 1,228 ms
24,192 KB
testcase_48 AC 1,224 ms
24,144 KB
testcase_49 AC 1,237 ms
23,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

class action {
public:
	static constexpr int D = 14;
	static constexpr int ACTION_BUILD = 1;
	static constexpr int ACTION_LEVEL = 2;
	static constexpr int ACTION_MONEY = 3;
	int tp, id;
	action() : tp(-1), id(-1) {}
	action(int tp_) : tp(tp_), id(-1) {
		assert(tp == 2 || tp == 3);
	}
	action(int tp_, int id_) : tp(tp_), id(id_) {
		assert(tp == 1 && 0 <= id && id < D * (D - 1) * 2);
	}
	string to_string() const {
		assert(tp != -1);
		if (tp == 2 || tp == 3) {
			return std::to_string(tp);
		}
		int xa, ya, xb, yb;
		if (id < D * (D - 1)) {
			xa = id / D;
			ya = id % D;
			xb = xa + 1;
			yb = ya;
		}
		else {
			xa = (id - D * (D - 1)) / (D - 1);
			ya = (id - D * (D - 1)) % (D - 1);
			xb = xa;
			yb = ya + 1;
		}
		// output in 1-indexed
		return std::to_string(tp) + " " + std::to_string(xa + 1) + " " + std::to_string(ya + 1) + " " + std::to_string(xb + 1) + " " + std::to_string(yb + 1);
	}
};

uint64_t seed = 123456789;
uint64_t xorshift64() {
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
	return seed;
}

int main() {
	// step #1. initial input
	const int INF = 1012345678;
	const int D = action::D;
	int N, T;
	cin >> N >> T;
	vector<int> X(N), Y(N);
	for (int i = 0; i < N; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		X[i] = (a - 1) * D + (b - 1);
		Y[i] = (c - 1) * D + (d - 1);
	}

	// step #2. make graph-like list of citizens
	vector<int> deg(D * D);
	for (int i = 0; i < N; i++) {
		deg[X[i]] += 1;
		deg[Y[i]] += 1;
	}
	vector<vector<int> > G(D * D);
	for (int i = 0; i < N; i++) {
		if (deg[X[i]] > deg[Y[i]] || (deg[X[i]] == deg[Y[i]] && X[i] < Y[i])) {
			G[X[i]].push_back(Y[i]);
		}
		else {
			G[Y[i]].push_back(X[i]);
		}
	}
	int cnt = 0;
	for (int i = 0; i < D * D; i++) {
		if (deg[i] >= 1) {
			cnt += 1;
		}
	}

	// step #3. function to calculate score
	auto getdist = [&](const vector<int>& road) {
		vector<vector<int> > dist(D * D, vector<int>(D * D, INF));
		vector<int> q1(D * D);
		vector<int> q2(D * D);
		for (int i = 0; i < D * D; i++) {
			dist[i][i] = 0;
			int ql1 = 0, qr1 = 1;
			int ql2 = 0, qr2 = 0;
			q1[0] = i;
			while (ql1 != qr1 || ql2 != qr2) {
				int c1 = (ql1 != qr1 ? q1[ql1] : INF);
				int c2 = (ql2 != qr2 ? q2[ql2] : INF);
				int pos = -1, curdist = 0;
				if (c1 <= c2) {
					curdist = (c1 >> 12);
					pos = (c1 & ((1 << 12) - 1));
					ql1 += 1;
				}
				else {
					curdist = (c2 >> 12);
					pos = (c2 & ((1 << 12) - 1));
					ql2 += 1;
				}
				int px = pos / D, py = pos % D;
				// direction 1: down
				if (px != D - 1 && road[px * D + py] == 0) {
					if (dist[i][pos + D] > curdist + 1000) {
						dist[i][pos + D] = curdist + 1000;
						q1[qr1++] = (dist[i][pos + D] << 12) | (pos + D);
					}
				}
				if (px != D - 1 && road[px * D + py] == 1) {
					if (dist[i][pos + D] > curdist + 223) {
						dist[i][pos + D] = curdist + 223;
						q2[qr2++] = (dist[i][pos + D] << 12) | (pos + D);
					}
				}
				// direction 2: up
				if (px != 0 && road[(px - 1) * D + py] == 0) {
					if (dist[i][pos - D] > curdist + 1000) {
						dist[i][pos - D] = curdist + 1000;
						q1[qr1++] = (dist[i][pos - D] << 12) | (pos - D);
					}
				}
				if (px != 0 && road[(px - 1) * D + py] == 1) {
					if (dist[i][pos - D] > curdist + 223) {
						dist[i][pos - D] = curdist + 223;
						q2[qr2++] = (dist[i][pos - D] << 12) | (pos - D);
					}
				}
				// direction 3: right
				if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 0) {
					if (dist[i][pos + 1] > curdist + 1000) {
						dist[i][pos + 1] = curdist + 1000;
						q1[qr1++] = (dist[i][pos + 1] << 12) | (pos + 1);
					}
				}
				if (py != D - 1 && road[D * (D - 1) + px * (D - 1) + py] == 1) {
					if (dist[i][pos + 1] > curdist + 223) {
						dist[i][pos + 1] = curdist + 223;
						q2[qr2++] = (dist[i][pos + 1] << 12) | (pos + 1);
					}
				}
				// direction 4: left
				if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 0) {
					if (dist[i][pos - 1] > curdist + 1000) {
						dist[i][pos - 1] = curdist + 1000;
						q1[qr1++] = (dist[i][pos - 1] << 12) | (pos - 1);
					}
				}
				if (py != 0 && road[D * (D - 1) + px * (D - 1) + py - 1] == 1) {
					if (dist[i][pos - 1] > curdist + 223) {
						dist[i][pos - 1] = curdist + 223;
						q2[qr2++] = (dist[i][pos - 1] << 12) | (pos - 1);
					}
				}
			}
		}
		return dist;
	};

	// step #4. process queries
	int current_money = 1000000;
	int current_level = 1;
	int current_score = 0;
	int used_roads = 0;
	vector<int> road(D * (D - 1) * 2, 0);
	vector<vector<int> > dist = getdist(road);
	auto calc = [&](const vector<int>& road) {
		int answer = 0;
		for (int i = 0; i < N; i++) {
			answer += (dist[X[i]][Y[i]] * 287) % 1000;
		}
		return answer;
	};
	vector<action> a(T);
	vector<int> level(T + 1), money(T + 1), score(T + 1);
	for (int i = 0; i < T; i++) {
		// decide action
		int required_money = int(10000000 / sqrt(current_level));
		if (i < 37) {
			a[i] = action(action::ACTION_LEVEL);
		}
		else if (used_roads == 0 && current_money < required_money) {
			a[i] = action(action::ACTION_MONEY);
		}
		else {
			if (current_money >= required_money) {
				int opt_choice = -1;
				int opt_score = -INF;
				for (int j = 0; j < D * (D - 1) * 2; j++) {
					if (road[j] == 0) {
						int va, vb;
						if (j < D * (D - 1)) {
							va = j;
							vb = j + D;
						}
						else {
							va = (j - D * (D - 1)) / (D - 1) * D + (j - D * (D - 1)) % (D - 1);
							vb = va + 1;
						}
						int subscore = 0;
						for (int k = 0; k < N; k++) {
							int d1 = dist[X[k]][Y[k]];
							int d2 = dist[X[k]][va] + dist[Y[k]][vb] + 223;
							int d3 = dist[X[k]][vb] + dist[Y[k]][va] + 223;
							int d4 = min(d1, min(d2, d3));
							subscore += (d4 * 287) % 1000;
						}
						if (opt_score < subscore) {
							opt_score = subscore;
							opt_choice = j;
						}
					}
				}
				a[i] = action(action::ACTION_BUILD, opt_choice);
				used_roads += 1;
			}
			else {
				a[i] = action(action::ACTION_LEVEL);
			}
		}
		// process action
		if (a[i].tp == action::ACTION_BUILD) {
			road[a[i].id] = 1;
			used_roads += 1;
			dist = getdist(road);
			current_money -= required_money;
			current_score = calc(road);
		}
		if (a[i].tp == action::ACTION_LEVEL) {
			current_level += 1;
		}
		if (a[i].tp == action::ACTION_MONEY) {
			current_money += 50000;
		}
		current_money += current_score * 60;
		money[i + 1] = current_money;
		level[i + 1] = current_level;
		score[i + 1] = current_score;
	}
	int best_money = -INF;
	int best_sep = -1;
	for (int i = 0; i <= T; i++) {
		int final_money = money[i] + (score[i] * 60 + 50000) * (T - i);
		if (best_money < final_money) {
			best_money = final_money;
			best_sep = i;
		}
	}
	for (int i = best_sep; i < T; i++) {
		a[i] = action(action::ACTION_MONEY);
	}
	for (int i = 0; i < T; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		cout << a[i].to_string() << endl;
	}
	cerr << "level = " << level[best_sep] << ", money = " << best_money << ", score = " << score[best_sep] << " (sep = " << best_sep << ")" << endl;

	return 0;
}
0