Submission #191319

#	Time	Username	Problem	Language	Result	Execution time	Memory
191319		atoiz	Naan (JOI19_naan)	C++14	29 / 100	37 ms	7964 KiB

naan

/*input
7 1
1
2
3
4
5
6
7
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// credit: https://codeforces.com/blog/entry/66022?#comment-500539

struct Frac
{
	uint64_t nume, demo;

	Frac(uint64_t _nume = 0, uint64_t _demo = 1): nume(_nume), demo(_demo) {}

	bool operator<(const Frac fr) const
	{
		return nume * fr.demo < fr.nume * demo;
	}

	bool operator<=(const Frac fr) const
	{
		return nume * fr.demo <= fr.nume * demo;
	}

	bool operator==(const Frac fr) const
	{
		return nume * fr.demo == fr.nume * demo;
	}

	Frac operator+(const uint64_t x) const
	{
		return {nume + demo * x, demo};
	}

	Frac operator-(const uint64_t x) const
	{
		return {nume - demo * x, demo};
	}

	Frac operator/ (const uint64_t x) const
	{
		return {nume, demo * x};
	}

	friend ostream& operator<< (ostream &os, const Frac fr)
	{
		return os << fr.nume << ' ' << fr.demo;
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	uint32_t N, L;
	cin >> N >> L;
	vector<vector<uint32_t>> V(N, vector<uint32_t>(L));
	for (auto &vec : V) for (auto &i : vec) cin >> i;

	vector<vector<Frac>> joints(N, vector<Frac>(N, {0, 1}));
	for (uint32_t person = 0; person < N; ++person) {
		uint32_t total = accumulate(V[person].begin(), V[person].end(), (uint32_t) 0);

		uint32_t flavor = 0, happiness = 0;
		for (uint32_t split = 1; split < N; ++split) {
			Frac target(total * split, N);

			while (Frac(happiness + V[person][flavor], 1) <= target) {
				happiness += V[person][flavor];
				++flavor;
			}

			joints[person][split] = ((target - happiness) / V[person][flavor]) + flavor;
		}
	}

	vector<uint32_t> P(N);
	vector<bool> used(N, false);
	for (uint32_t joint = 1; joint < N; ++joint) {
		uint32_t candidate = N;
		for (uint32_t person = 0; person < N; ++person) {
			if ((not used[person]) and (candidate == N or joints[person][joint] < joints[candidate][joint])) {
				candidate = person;
			}
		}
		P[joint - 1] = candidate;
		used[candidate] = true;
		cout << joints[candidate][joint] << '\n';
	}

	for (uint32_t person = 0; person < N; ++person) {
		if (not used[person]) {
			P[N - 1] = person;
			break;
		}
	}

	for (auto person : P) {
		cout << person + 1 << ' ';
	}

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71