Atcoder解いてみた AtCoder Beginner Contest C - Standings

AtCoder Beginner Contest C - Standings

問題はこちら

回答

浮動小数演算による誤差を発生させずに評価値を比較する方法の学習
ソート時のカスタム関数の書き方の学習

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>


int N;

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;

	std::vector<std::tuple<long long, long long, int>> abi;

	for (int i = 1; i <= N; i++) {
		long long a, b;
		std::cin >> a >> b;
		abi.emplace_back(a, b, i);
	}

	auto cmp = [](const std::tuple<long long, long long, int>& abi1, const std::tuple<long long, long long, int>& abi2) {
		const auto [a1, b1, i1] = abi1;
		const auto [a2, b2, i2] = abi2;

		// a1 / (a1 + b1) > a2 / (a2 + b2)
		// <=> a1 * (a2 + b2) > a2 * (a1 + b1)
		long long left = a1 * (a2 + b2);
		long long right = a2 * (a1 + b1);

		if (left != right) {
			return left > right; // 成功率が高い順
		}
		// 成功率が同じ場合は番号が小さい順
		return i1 < i2;
	};

	std::sort(abi.begin(), abi.end(), cmp);

	for (const auto& [a, b, i] : abi) {
		std::cout << i << " ";
	}

	return 0;
}