結果

問題 No.5023 Airlines Optimization
コンテスト
ユーザー e869120
提出日時 2026-02-21 20:53:54
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 2,723 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,302 ms
コンパイル使用メモリ 226,840 KB
実行使用メモリ 7,972 KB
スコア 23,520,140
最終ジャッジ日時 2026-02-25 20:31:55
合計ジャッジ時間 7,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// ====================================================================================================================
// Functions
// ====================================================================================================================
namespace {
	unsigned int seed = 869120;
	unsigned int Rand() { seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return (seed & 2147483647); }
	double Randouble() { return Rand() / 2147483648.0; }
	double GetTime() { return 1.0 * clock() / CLOCKS_PER_SEC; }
};

struct Info {
	int a, s, b, t;
};

int get_duration(int px, int py, int qx, int qy) {
	double dst = sqrt(1.0 * ((px - qx) * (px - qx) + (py - qy) * (py - qy)));
	double tm = (60.0 * dst / 800.0) + 40.0;
	return (int)((tm + 4.999999999) / 5.0) * 5;
}

int convert(string s) {
	int tm = 60 * stoi(s.substr(0, 2)) + stoi(s.substr(3, 2));
	return tm;
}

string convert2(int tm) {
	string hh = to_string(tm / 60); while (hh.size() < 2) hh = "0" + hh;
	string mm = to_string(tm % 60); while (mm.size() < 2) mm = "0" + mm;
	return hh + ":" + mm;
}



// ====================================================================================================================
// Main Part
// ====================================================================================================================
int main() {
	// step 1. input
	int N, R; cin >> N >> R;
	vector<int> x(N), y(N), w(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> w[i];
	}
	int M; cin >> M;
	vector<Info> v(M);
	for (int i = 0; i < M; i++) {
		string s1, s2;
		cin >> v[i].a >> s1 >> v[i].b >> s2;
		v[i].s = convert(s1);
		v[i].t = convert(s2);
	}
	int K; cin >> K;

	// step 2. prepare
	vector<int> sum(N + 1, 0);
	for (int i = 0; i < N; i++) {
		sum[i + 1] = sum[i] + w[i];
	}

	// step 3. solve
	auto get_position = [&]() -> int {
		int x = Rand() % sum[N] + 1;
		return lower_bound(sum.begin(), sum.end(), x) - sum.begin() - 1;
	};
	for (int i = 0; i < K; i++) {
		int current_time = 360 + 5 * (rand() % 10);
		int pos = get_position();
		vector<Info> plan;
		while (true) {
			int nex_pos;
			while (true) {
				nex_pos = get_position();
				if (pos != nex_pos) break;
			}
			int goal_time = current_time + get_duration(x[pos], y[pos], x[nex_pos], y[nex_pos]);
			if (goal_time > 1260) break;
			plan.push_back(Info{pos, current_time, nex_pos, goal_time});
			goal_time += 5 * (rand() % 3);
			current_time = goal_time;
			pos = nex_pos;
		}
		
		// output
		cout << plan.size() << endl;
		for (int i = 0; i < plan.size(); i++) {
			cout << plan[i].a + 1 << " " << convert2(plan[i].s) << " " << plan[i].b + 1 << " " << convert2(plan[i].t) << endl;
		}
	}
	return 0;
}
0