結果

問題 No.5020 Averaging
ユーザー square1001square1001
提出日時 2024-02-25 17:14:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,495 bytes
コンパイル時間 2,219 ms
コンパイル使用メモリ 210,572 KB
実行使用メモリ 6,676 KB
スコア 68,859,554
最終ジャッジ日時 2024-02-25 17:14:37
合計ジャッジ時間 4,147 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main() {
	// step #1. input
	int N;
	cin >> N;
	vector<double> A(N), B(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		A[i] -= 5.0e+17;
		B[i] -= 5.0e+17;
	}
	
	// step #2. greedy
	double bestscore = 1.0e+99;
	vector<int> bestdepth;
	for (int i = 0; i < N; i++) {
		vector<int> depth(N, -1);
		depth[i] = 1;
		double x = A[i] * 0.5;
		double y = B[i] * 0.5;
		for (int j = 2; j <= N; j++) {
			double mul = pow(0.5, min(j, N - 1));
			double subbest = 1.0e+99;
			int subpos = -1;
			for (int k = 0; k < N; k++) {
				if (depth[k] == -1) {
					double nx = x + A[k] * mul;
					double ny = y + B[k] * mul;
					if (subbest > max(abs(nx), abs(ny))) {
						subbest = max(abs(nx), abs(ny));
						subpos = k;
					}
				}
			}
			depth[subpos] = min(j, N - 1);
			x += A[subpos] * mul;
			y += B[subpos] * mul;
		}
		if (bestscore > max(abs(x), abs(y))) {
			bestscore = max(abs(x), abs(y));
			bestdepth = depth;
		}
	}
	
	// step #3. construction
	vector<array<int, 2> > answer;
	vector<int> curdepth = bestdepth;
	while (curdepth[0] != 0) {
		int p1 = max_element(curdepth.begin(), curdepth.end()) - curdepth.begin();
		int p2 = max_element(curdepth.begin() + p1 + 1, curdepth.end()) - curdepth.begin();
		answer.push_back({p1, p2});
		curdepth[p1] -= 1;
		curdepth[p2] = -1;
	}
	
	// step #4. output
	cout << answer.size() << endl;
	for (array<int, 2> v : answer) {
		cout << v[0] + 1 << ' ' << v[1] + 1 << endl;
	}
	
	return 0;
}
0